fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define DragonBui 0
  5. #define Task "Test"
  6. #define int long long
  7. #define el '\n'
  8. #define cnt_bit_1 __builtin_popcountll
  9. #define float double
  10. #define IO freopen(Task".inp","r",stdin); freopen(Task".out","w",stdout);
  11. #define pii pair<int,int>
  12. #define fi first
  13. #define se second
  14. #define pb push_back
  15.  
  16. const int N=2e5+5;
  17. const int INF=1e18;
  18. const int MOD=1e9+7;
  19.  
  20. int n , cL;
  21. string s;
  22. int f[15] , cnt[10];
  23. int ans = 0;
  24.  
  25. void precompute()
  26. {
  27.     f[0] = 1;
  28.     for(int i = 1; i <= 13; i++) f[i] = f[i - 1] * i;
  29. }
  30.  
  31. int calc()
  32. {
  33.     int id = f[cL];
  34.     for(int i = 0; i <= 9; i++) id /= f[cnt[i]];
  35.  
  36.     int w = 0;
  37.     if(cnt[0] > 0)
  38.     {
  39.         w = f[cL - 1];
  40.         cnt[0]--;
  41.         for (int i = 0; i <= 9; i++) w /= f[cnt[i]];
  42.         cnt[0]++;
  43.     }
  44.     return id - w;
  45. }
  46.  
  47. int cntles()
  48. {
  49.     int res = 0;
  50.     vector<int> cur_cnt(10);
  51.     for(int i = 0; i <= 9; i++) cur_cnt[i] = cnt[i];
  52.  
  53.     for(int i = 0; i < cL; i++)
  54.     {
  55.         int cdr = s[i] - '0';
  56.  
  57.         for(int d = 0; d < cdr; d++)
  58.         {
  59.             if(i == 0 && d == 0) continue;
  60.             if(cur_cnt[d] > 0)
  61.             {
  62.                 cur_cnt[d]--;
  63.                 int id = f[cL - 1 - i];
  64.                 for (int x = 0; x <= 9; x++) id /= f[cur_cnt[x]];
  65.                 res += id;
  66.                 cur_cnt[d]++;
  67.             }
  68.         }
  69.  
  70.         if(cur_cnt[cdr] > 0) cur_cnt[cdr]--;
  71.         else break;
  72.  
  73.         if(i == cL - 1) res++;
  74.     }
  75.     return res;
  76. }
  77.  
  78. void backtrack(int digit, int rem, int sum, int nw1)
  79. {
  80.     if(rem == 0)
  81.     {
  82.         if(sum > 0 && sum % cL == 0 && nw1 % sum == 0)
  83.         {
  84.             if(cL < n) ans += calc();
  85.             else ans += cntles();
  86.         }
  87.         return;
  88.     }
  89.  
  90.     if(digit > 9) return;
  91.  
  92.     for(int k = 0; k <= rem; k++)
  93.     {
  94.         cnt[digit] = k;
  95.  
  96.         int nw = nw1;
  97.         if(k > 0)
  98.         {
  99.             if(digit == 0) nw = 0;
  100.             else
  101.             {
  102.                 for(int i = 0; i < k; i++) nw *= digit;
  103.             }
  104.         }
  105.  
  106.         backtrack(digit + 1, rem - k, sum + digit * k, nw);
  107.         cnt[digit] = 0;
  108.     }
  109. }
  110.  
  111. signed main()
  112. {
  113.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  114.     //IO
  115.  
  116.     precompute();
  117.  
  118.     cin >> s;
  119.  
  120.     n = s.size();
  121.  
  122.     for(int L = 1; L <= n; L++)
  123.     {
  124.         cL = L;
  125.         backtrack(0, L, 0, 1);
  126.     }
  127.  
  128.     cout << ans;
  129.  
  130.     return (DragonBui);
  131. }
  132.  
  133. /// Long Bùi
  134. /// TrQuocann - TH & THCS & THPT SAO VIET - 10a1
  135.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/iC8dVI
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!