容易想到状态dp[n][S][m]（S是数字出现的集合），表示前n位用了数字集S且模k余数是m的方案数。
利用 (xy)base % k = ( x*base+y ) % k = (( x%k ) * base + y) % k ，进行状态第三维的转移。
不过d[16][216][20]有2000多W的状态数，且不说超时的问题，内存早已超过限制了。
可以发现，S这一维其实就包含了n这一维的信息了，所以只要二维就能表示状态。
dp[m][S]表示，数字集为s且模k余数为m的方案数
状态的转移，从前往后不好处理余数，所以我从后往前更新状态的值，所谓的“我为人人”：
从dp[m][S]出发，更新dp[(m*base+y)%k][S']，其中S'-S={y}。
#include<cstdio>
#include<cstring>
using namespace std;
long long d[][<<];
int symbol[];
int main(){
for(int i=;i<;++i) symbol[i+'']=i;
for(int i=;i<;++i) symbol[i-+'A']=i; int t,base,mod;
char str[];
scanf("%d",&t);
for(int cse=; cse<=t; ++cse){
scanf("%d%d%s",&base,&mod,str);
int n=strlen(str);
memset(d,,sizeof(d));
d[][]=;
for(int i=; i<(<<n); ++i){
for(int j=; j<mod; ++j){
for(int k=; k<n; ++k){
if((i>>k)&) continue;
d[(j*base+symbol[str[k]])%mod][i|(<<k)]+=d[j][i];
}
}
}
printf("Case %d: %lld\n",cse,d[][(<<n)-]);
}
return ;
}