BZOJ 1072 「SCOI2007」排列

发表于 | 分类于 |

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

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

不过注意到相同的数字换顺序仍然会被计算，于是将答案除以 \(\prod\limits_{i=0}^9 \mathrm{cnt}_i!\)，其中 \(\mathrm{cnt}_i\) 表示 \(i\) 在 \(s\) 中的出现次数。

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#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]);
    }
}