LightOJ - 1021 - Painful Bases

As you know that sometimes base conversion is a painful task. But still there are interesting facts in bases.

For convenience let's assume that we are dealing with the bases from 2 to 16. The valid symbols are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E and F. And you can assume that all the numbers given in this problem are valid. For example 67AB is not a valid number of base 11, since the allowed digits for base 11 are 0 to A.

Now in this problem you are given a base, an integer K and a valid number in the base which contains distinct digits. You have to find the number of permutations of the given number which are divisible by K. K is given in decimal.

For this problem, you can assume that numbers with leading zeroes are allowed. So, 096 is a valid integer.

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a blank line. After that there will be two integers, base (2 ≤ base ≤ 16) and K (1 ≤ K ≤ 20). The next line contains a valid integer in that base which contains distinct digits, that means in that number no digit occurs more than once.

Output

For each case, print the case number and the desired result.

Sample Input	Output for Sample Input
3 2 2 10 10 2 5681 16 1 ABCDEF0123456789	Case 1: 1 Case 2: 12 Case 3: 20922789888000

Solution:

1. #include <bits/stdc++.h>
2. #define pb push_back
3. using namespace std;
4. typedef long long LL;
5. const int S = 100003;
6. const int MOD = 1e9+7;
7. const double pi = 2 * acos (0.0);
8.  
9. int _Int(){int x; scanf("%d", &x); return x;}
10. LL _LLi(){LL x; scanf("%lld", &x); return x;}
11. void pruts(){puts("-1");exit(EXIT_SUCCESS);}
12.  
13. int dirX[]={1, 0, -1, 0, 1, -1, 1, -1};
14. int dirY[]={0, 1, 0, -1, 1, -1, -1, 1};
15. int rX[] = {1, 1, 2, 2, -1, -1, -2, -2};
16. int rY[] = {2, -2, 1, -1, 2, -2, 1, -1};
17.  
18. template <class T> T tri_Area( T x1, T y1, T x2, T y2, T x3, T y3 ){ return abs( x1*( y2-y3 ) - y1*( x2-x3 ) + ( x2*y3-x3*y2 ) );};
19. template <class T> T Distance( T x1, T y1, T x2, T y2 ){ return sqrt( ( x1-x2 ) * ( x1-x2 ) + ( y1-y2 ) * ( y1-y2 ) ); };
20. template <class T> T bigMod( T n, T p, T m ){ if( p == 0 )return 1; if( p&1 )return ( n*bigMod( n, p-1, m ) )%m; T x = bigMod( n, p/2, m ); return ( x*x )%m; };
21.  
22. int sset(int N, int pos){return N=N|(1<<pos);}
23. bool check(int N, int pos){return (bool)(N&(1<<pos));}
24. int reset(int N, int pos){return N=N&~(1<<pos);}
25. /*******************###########################################********************
26. ********************##   MD. YA-SEEN ARAFAT(ThunderStroke)   ##********************
27. ********************##    CSE, University of Asia Pacific    ##********************
28. ********************###########################################********************/
29.  
30. int A[ 16 ], sz, n, k;
31. LL dp[ (1<<16)+2 ][ 20 ];
32.  
33. LL PainfulBases ( int mask, int remdr ){
34.     if( mask == ( 1<< sz)-1 )return ( ( !remdr )? 1LL : 0LL );
35.     if( dp[ mask ][ remdr ] != -1 )return dp[ mask ][ remdr ];
36.     LL ret = 0LL;
37.     for( int i = 0; i < sz; i++ ){
38.         if( !( mask&( 1<<i ) ) ){
39.             int rem = ( ( remdr * n ) + A[ i ] );
40.             ret += PainfulBases( ( mask | ( 1<<i ) ), ( rem%k ) );
41.         }
42.     }
43.     return dp[ mask ][ remdr ] = ret;
44. }
45.  
46. void Love(){
47.     int t = _Int(), cs = 0;
48.     while( t-- ){
49.         memset( dp, -1, sizeof(dp) );
50.         char s[ 16 ];
51.         n = _Int();
52.         k = _Int();
53.         scanf( "%s", s );
54.         sz = strlen( s );
55.         for( int i = 0; i < sz; i++ )
56.             A[ i ] = ( s[ i ] >= 'A' && s[ i ] <= 'Z' )? ( s[ i ]-'A'+10 ) : ( s[ i ]-'0' );
57.         LL ans = PainfulBases( 0, 0 );
58.         printf( "Case %d: %lld\n", ++cs, ans );
59.     }
60. }
61.  
62. int main(){
63.     #ifndef ONLINE_JUDGE
64. //        freopen("in.txt", "r", stdin);
65. //        freopen("n.txt", "w", stdout);
66.     #endif
67.     Love();
68.     return 0;
69. }