lightoj1021

CODE

#include <iostream>
#include <cstring>
#include <cstdlib>
#define CL(a,b) memset(a,b,sizeof(a))
using namespace std;

long long dp[1<<16][20];
int ix[16];
char s[105];
int n,k,nCase;
int main()
{
        int t;
        cin >>t;
        while(t--)
        {
                cin >>n>>k>>s;
                int len=strlen(s);
                CL(ix,0);
                for(int i=0;i<len;i++)
                {
                        if(s[i]<='Z'&&s[i]>='A')ix[s[i]-'A'+10]=1;
                        else ix[s[i]-'0']=1;
                }
                CL(dp,0);

                for(int i=0;i<n;i++)
                {
                        if(ix[i])dp[1<<i][i%k]=1;
                }
                for(int i=0;i<(1<<n);i++)
                        for(int j=0;j<k;j++)
                {
                        if(dp[i][j]==0)continue;
                        for(int l=0;l<n;l++)
                        {
                                if(((1<<l)&i)==0&&ix[l])
                                        dp[i|(1<<l)][(j*n+l)%k]+=dp[i][j];
                        }
                }
                cout << "Case "<<++nCase<<": ";
                int cur=0;
                for(int i=0;i<n;i++)if(ix[i])cur|=1<<i;
                cout << dp[cur][0]<<endl;
        }

        return 0;
}