BZOJ 1072 「SCOI2007」排列

状压水题……
貌似是一年前抄刷的？回来看一看……

排列！|s|≤10！这不显然状压……
设 fS,i 表示选过的 s 串中的位置的集合为 S，排列对 d 取模的结果为 i 的方案数。
转移 SB 不讲了。

不过注意到相同的数字换顺序仍然会被计算，于是将答案除以 9∏i=0cnti!，其中 cnti 表示 i 在 s 中的出现次数。

代码：

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 10;
const int D = 1e3;
int T,n,d,full,fac[N + 5],cnt[10];
char s[N + 5];
int f[(1 << N) + 5][D + 5];
int main()
{
    scanf("%d",&T),fac[0] = 1;
    for(register int i = 1;i <= N;++i)
        fac[i] = fac[i - 1] * i;
    for(;T;--T)
    {
        scanf("%s%d",s + 1,&d),n = strlen(s + 1),memset(cnt,0,sizeof cnt),memset(f,0,sizeof f),full = (1 << n) - 1;
        for(register int i = 1;i <= n;++i)
            ++cnt[s[i] -= '0'];
        f[0][0] = 1;
        for(register int i = 0;i <= full;++i)
            for(register int j = 0;j < d;++j)
                for(register int k = 1;k <= n;++k)
                    if(!(i & (1 << k - 1)))
                        f[i | (1 << k - 1)][(j * 10 + s[k]) % d] += f[i][j];
        for(register int i = 0;i < 10;++i)
            f[full][0] /= fac[cnt[i]];
        printf("%d\n",f[full][0]);
    }
}