[文章目录]
Description
给一个数字串s和正整数d, 统计s有多少种不同的排列能被d整除（可以有前导0）。例如123434有90种排列能被2整除，其中末位为2的有30种，末位为4的有60种。1<=d<=1000, 1<=T<=15
一眼爆搜，然后TLE？？？好像来回扫数组是否用到有点耗时？？？链表优化？？？算了，写正解吧。
一看d那么小显然是想让我们状压dp啊。（去你的！！！）
设dp[s][i]表示已经用了s这个状态选择的数码，除以d的余数是i的方案数。发现每次找到一位不为1的进行dp。时间复杂度O(len*2^len*d)？？？？反正过了。。
简单粗暴：!(s&(1<< k)) dp[s|(1<< k)][(i+q)%d]+=dp[s][i]
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll bas[1030],d;
int dp[1030][1000];
char st[20]; int a[20],n,num[20];
int main()
{
int T; scanf("%d",&T); bas[0]=1;
for(int s=1;s<(1<<10);++s) bas[s]=bas[s-(-s&s)]*10;
while(T--)
{
scanf("%s%lld",st+1,&d); n=strlen(st+1);
for(int i=1;i<=n;++i) a[i]=st[i]-'0';
memset(dp,0,sizeof dp);
dp[0][0]=1; ll tmp;
for(int s=0;s<(1<<n);++s)
{
for(int k=0;k!=n;++k)
if(!(s&(1<<k)))
{
tmp=bas[s]*a[k+1]%d;
for(int i=0;i!=d;++i)
dp[s|(1<<k)][(i+tmp>=d)?i+tmp-d:i+tmp]+=dp[s][i];
}
}
memset(num,0,sizeof num);
for(int i=1;i<=n;++i) num[a[i]]++,dp[(1<<n)-1][0]/=num[a[i]];
printf("%d\n",dp[(1<<n)-1][0]);
}
return 0;
}