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]);
}
}