[SCOI2007]排列

看了看数据范围。。。我艹。。。爆搜可过？

等等，冷静，让我看一眼题解。。。我艹。。。真可过。。。

emm。。。再冷静分析。。。emm。。。还是写状压吧。。。

这题主要的思路就是 f[i][j] 表示 在 i 号状态下 总和%d为 j 的情况

这样我们只用判断这个方案合不合法即可。。。

对了，因为有重复数字，所以要去重。。。

呆码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int T,p[15],a[15],n,d,num[15],f[1<<11][1010];
char ch[15];

int main()
{
    scanf("%d",&T);
    p[0]=1;
    for(int i=1;i<=9;i++) p[i]=p[i-1]*i;
    while(T--)
    {
        scanf("%s%d",ch,&d);
        n=strlen(ch);
        memset(num,0,sizeof(num));
        for(int i=1;i<=n;i++)
        {
            num[ch[i-1]-'0']++;
            a[i]=ch[i-1]-'0';
        }
        memset(f,0,sizeof(f));
        f[0][0]=1;
        for(int i=0;i<(1<<n);i++)
            for(int j=0;j<d;j++)
                if(f[i][j])
                    for(int k=1;k<=n;k++)
                        if((1<<(k-1)&i)==0)
                            f[i|(1<<(k-1))][(j*10+a[k])%d]+=f[i][j];
        for(int i=0;i<=9;i++) f[(1<<n)-1][0]/=p[num[i]];
        printf("%d
",f[(1<<n)-1][0]);
    }
}