题意

给一个数字串$s$和正整数$d$, 统计$s$有多少种不同的排列能被$d$整除

数据范围：$s$的长度$\le 10,1 \le d \le 1000$

题解

直接计算整除的较为麻烦，可以状压使用过的数$d$并记录当前数模$d$的余数，再来表示方案数
用$f[i][j]$表示选用过的数状态压缩为$i$，当前余数为$j$
易得状态转移方程$$f[i|(1<<j)][(k*10+a[j])\%d]=sum(f[i][k])$$其中$j$为不在$i$中的数，$k$为余数
但是若有重复数字会多次计算，我们记下这个重复的次数$cnt$，那么答案需要除以$A_{cnt}^{cnt}=cnt!$

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int D=1000+10;
int t,l,d;
char s[10];
int a[10];
int ans;
int fac[10],cnt[10],dp[1<<11][D];
int main(){
    scanf("%d",&t);
    fac[0]=1;
    for(int i=1;i<10;i++)
        fac[i]=fac[i-1]*i;
    for(;t--;){
        memset(cnt,0,sizeof(cnt));
        memset(dp,0,sizeof(dp));
        scanf("%s%d",s,&d);
        l=strlen(s);
        for(int i=0;i<l;i++)
            cnt[a[i]=s[i]-'0']++;
        dp[0][0]=1;
        for(int i=0;i<(1<<l);i++)
            for(int j=0;j<l;j++){
                if(i&(1<<j))
                    continue;
                for(int k=0;k<d;k++)
                    dp[i|(1<<j)][(k*10+a[j])%d]+=dp[i][k];
            }
        ans=dp[(1<<l)-1][0];
        for(int i=0;i<10;i++)
            ans/=fac[cnt[i]];
        printf("%d\n",ans);
    }
    return 0;
}