Guest User

491E

a guest
Jun 23rd, 2018
1,278
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. long long fact[20];
  6.  
  7. set<string> was;
  8. int c0[10];
  9. int c[10];
  10.  
  11. void split(string s, int *c) {
  12.     for (int i = 0; i < 10; i++)
  13.         c[i] = 0;
  14.     for (char ch : s)
  15.         c[ch - 48]++;
  16. }
  17.  
  18. long long getCount() {
  19.     long long ans = fact[accumulate(c, c + 10, 0)];
  20.     for (int i = 0; i < 10; i++)
  21.         ans /= fact[c[i]];
  22.     return ans;
  23. }
  24.  
  25. long long getans(string s) {
  26.     split(s, c);
  27.  
  28.     // check whether the string contains all digits
  29.     for (int i = 0; i < 10; i++)
  30.         if (c0[i] && !c[i])
  31.             return 0;
  32.  
  33.     // check whether we already processed such string
  34.     sort(s.begin(), s.end());
  35.     if (was.count(s))
  36.         return 0;
  37.     was.insert(s);
  38.  
  39.     long long ans = getCount();
  40.     if (c[0] > 0) {
  41.         c[0]--;
  42.         ans -= getCount();
  43.     }
  44.  
  45.     return ans;
  46. }
  47.  
  48. int main() {
  49.     fact[0] = 1;
  50.     for (int i = 1; i < 20; i++)
  51.         fact[i] = i * fact[i - 1];
  52.  
  53.     string n;
  54.     cin >> n;
  55.  
  56.     int k = n.length();
  57.     split(n, c0);
  58.  
  59.     long long ans = 0;
  60.     for (int i = 1; i <= (1 << k); i++) {
  61.         string c;
  62.         for (int j = 0; j < k; j++)
  63.             if (i & (1 << j))
  64.                 c += n[j];
  65.         ans += getans(c);
  66.     }
  67.  
  68.     cout << ans;
  69. }
RAW Paste Data