fork download
copy 
  1. /*In the name of Almighty Allah*/
  2.  
  3. #include<bits/stdc++.h>
  4.  
  5. #define pb          push_back
  6. #define mp          make_pair
  7. #define Fill(a,b) memset (a, b, sizeof a)
  8. #define all(a)      (a).begin(),(a).end()
  9. #define F           first
  10. #define S           second
  11. #define sz(x)       (int)x.size()
  12. #define mod         1000000007
  13. #define For(i,a,b)  for(int i=a;i<b;i++)
  14. #define rof(i,a,b)  for (int i=a;i>=b;i--)
  15.  
  16. using namespace std;
  17.  
  18. typedef long long       ll;
  19. typedef double          dl;
  20. typedef vector<int>     vi;
  21.  
  22. int Set(int N,int pos){return N=N | (1<<pos);}
  23. int reset(int N,int pos){return N= N & ~(1<<pos);}
  24. bool check(int N,int pos){return (bool)(N & (1<<pos));}
  25.  
  26. void dbga ( int a[], int s )
  27. {
  28.     For ( i, 0, s ) cout << a[i] << " ";
  29.     cout << endl;
  30. }
  31.  
  32. void dbgv ( vector < int > v )
  33. {
  34.     For ( i, 0, sz(v) ) cout << v[i] << " ";
  35.     cout << endl;
  36. }
  37.  
  38. void rev ( int a[], int s )
  39. {
  40.     for ( int i = 0,j = s-1; i < s/2; i++, j-- ) {
  41.         swap ( a[i], a[j] );
  42.     }
  43. }
  44.  
  45.  
  46. string to_s(int t)
  47. {
  48.   stringstream ss;
  49.   ss << t;
  50.   return ss.str();
  51. }
  52.  
  53. unsigned long long mypow ( int a, int b )
  54. {
  55.     unsigned long long  ret = 1;
  56.     For ( i, 1, b+1 ) {
  57.         ret *= a;
  58.     }
  59.     return ret;
  60. }
  61.  
  62.  
  63. struct edge {
  64.     int w,s;
  65. };
  66.  
  67. bool cmp ( const edge &a, const edge &b )
  68. {
  69.     return a.w < b.w;
  70. }
  71.  
  72. ll gcd(ll a, ll b) { return !a ? b : gcd(b % a, a); }
  73. ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
  74.  
  75. int tx[] = { 1, -1, 0, 0 };
  76. int ty[] = { 0, 0, 1, -1 };
  77.  
  78.  
  79. /*
  80. bool isprime[100123];
  81. vector < int > prime;
  82.  
  83. void seive ()
  84. {
  85.     int num = 100000, sqr = 340;
  86.     for ( int i = 3; i <= num; i+=2 ) isprime[i] = 1;
  87.  
  88.     for ( int i = 3; i <= sqr; i+=2 ) {
  89.         if ( isprime[i] ) {
  90.             for ( int j = i * i; j <=num; j+=(i*2) ) {
  91.                 isprime[j] = 0;
  92.             }
  93.         }
  94.     }
  95.  
  96.     prime.pb ( 2 );
  97.     isprime[2] = 1;
  98.  
  99.     for ( int i = 3; i <=num; i+=2 ) {
  100.         if ( isprime[i] ) prime.pb ( i );
  101.     }
  102. }
  103. */
  104.  
  105. unsigned long long  dp[1<<16][22];
  106. int n, base, k, a[20], p;
  107. char s[17];
  108.  
  109. unsigned long long call ( int mask, int md )
  110. {
  111.  
  112.     if ( mask == (1<<n)-1 ) {
  113.  
  114.         return ( md == 0 );
  115.     }
  116.  
  117.     if ( dp[mask][md] != -1 ) return dp[mask][md];
  118.     int  num = md, pos = 0;
  119.  
  120.     unsigned long long ret = 0;
  121.  
  122.     For ( i, 1, n ) if ( check ( mask, i ) ) pos++;
  123.  
  124.  
  125.  
  126.     rof ( i, n-1, 0 ) {
  127.         if ( check ( mask, i ) == 0 ) {
  128.             if ( base != 10 ) {
  129.                 num += ( a[i] ) * mypow ( base, pos );
  130.             }
  131.             else {
  132.                 num *= 10;
  133.                 num += a[i];
  134.             }
  135.  
  136.             ret += call ( Set ( mask, i ), num % k );
  137.         }
  138.     }
  139.  
  140.     return dp[mask][md] = ret;
  141. }
  142.  
  143. int main()
  144. {
  145.     //freopen("input.txt","r",stdin);
  146.     //freopen("output.txt","w",stdout);
  147.     ios_base::sync_with_stdio(0);
  148.     cin.tie(0);
  149.  
  150.     int t;
  151.     scanf ( "%d", &t );
  152.     For ( i, 1, t+1 ) {
  153.  
  154.         Fill ( dp, -1 );
  155.  
  156.         scanf ( "%d%d", &base, &k );
  157.         scanf ( "%s", &s );
  158.         n = strlen ( s );
  159.         For ( j, 0, n ) {
  160.             a[j] = s[j] - '0';
  161.             if ( a[j] > 9 ) a[j] -= 7;
  162.  
  163.         }
  164.  
  165.         printf ( "Case %d: %llu\n", i, call ( 0, 0 ) );
  166.     }
  167.  
  168.     return 0;
  169. }
  170.  
Success #stdin #stdout 0.59s 26496KB
comments (?)
stdin
copy 
2

16 12
F853AD64B1EC7290

16 18
8192BEFA70CD3564
stdout
copy 
Case 1: 2324797191360
Case 2: 1226335446000
https://ideone.com/2XjGaV
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
secret

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!