Light oj 1021 – Painful Bases

题意：  给一个B进制的数，一个10进制的数K，B进制数有x位，
　　　对着x位进行全排列的话，有x！种可能，
　　　问这x！的可能中，有多少种可以整除K，各个位置上的数字都不同。

思路：状态压缩，数位DP

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<string>
#include<algorithm>
#define MAXSIZE 70000
#define LL long long
using namespace std;
const long long INF = 1e18;//给一个B进制的数，一个10进制的数K，B进制数有x位，
//对着x位进行全排列的话，有x！种可能，
//问这x！的可能中，有多少种可以整除K，各个位置上的数字都不同。LL dp[MAXSIZE][];
int b,k,bit[MAXSIZE],len;
char str[MAXSIZE];
LL dfs(int pos,int st,int mod)
{
    if(pos < )
        return mod == ;
    if(dp[st][mod] != -)
        return dp[st][mod];
    LL ans = ;
    for(int i=;i<len;i++)
    {
        if(st & (<<i))
            continue;
        else
        {
            ans += dfs(pos-,st|(<<i),((mod*b)+bit[i])%k);
        }
    }    dp[st][mod] = ans;
    return ans;
}LL Solve()
{
    memset(dp,-,sizeof(dp));    len = strlen(str);
    int pos = ;
    for(int i=;i<len;i++)
    {
        if(str[i] >='' && str[i] <= '')
            bit[pos++] = str[i] - '';
        else
            bit[pos++] = str[i] - 'A' + ;
    }    LL ans = dfs(pos-,,);    return ans;
}int main()
{
    int T,cns=;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&b,&k);
        scanf("%s",str);
        LL ans = Solve();
        printf("Case %d: %lld\n",cns++,ans);
    }
    return ;
}