[BZOJ 1072][SCOI 2007] 排列

题目大意

给一个数字串 \(s\) 和正整数 \(d\), 统计 \(s\) 有多少种不同的排列能被 \(d\) 整除(可以有前导 \(0\))。多组数据。

\(1 \leqslant T \leqslant 15\)

\(1 \leqslant d \leqslant 1,000\)

\(s \ 的位数 \leqslant 10\)

题目链接

BZOJ 1072

CodeVS 2441

题解

状压 DP。

先考虑由给定的数字串中的部分数字组成的数的答案,然后在其后加一个还没有考虑的数字进行转移。用二进制的 \(1\)\(0\) 表示是否考虑了该数,\(f[i][j]\) 表示状态为 \(i\),模 \(d\) 余数为 \(j\) 时的答案,转移如下:

\[f[i][j] += f[i \; | \; 2^x][(j * 10 + num[x]) \; mod \; d], \; i \; \& \; 2^x = 0\]

不过这样在有重复数字时会重复计数,最后再除以 \(\prod cnt[i]!, \; (i = 1, \ 2, \ 3 \dots, \; 9)\) 即可(类比可重集合全排列,也要除以一个类似的东西)。

代码

当数据范围比较小的时候就不想给 MAXN 加上 \(5\)\(10\) 之类的了。。。(这个习惯明明就是为了方便自己从 \(1\) 开始标号啊)

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
#include <cstring>
#include <algorithm>
const int MAXN = 10;
const int MAXD = 1000;
char str[MAXN];
int num[MAXN], f[1 << MAXN][MAXD], cnt[MAXN], fact[MAXN + 1];
void calcFact() {
fact[0] = 1;
for (int i = 1; i <= MAXN; i++) fact[i] = fact[i - 1] * i;
}
void dp(int len, int d) {
memset(f, 0, sizeof (f));
f[0][0] = 1;
for (int i = 0; i < (1 << len); i++) {
for (int j = 0; j < d; j++) {
if (f[i][j]) {
for (int k = 0; k < len; k++) {
if ((i & (1 << k)) == 0)
f[i | (1 << k)][(j * 10 + num[k]) % d] += f[i][j];
}
}
}
}
}
int main() {
calcFact();
int T;
scanf("%d", &T);
while (T--) {
int d;
scanf("%s%d", str, &d);
int len = strlen(str);
memset(cnt, 0, sizeof (cnt));
for (int i = 0; i < len; i++) {
num[i] = str[i] - '0';
cnt[num[i]]++;
}
dp(len, d);
int ans = f[(1 << len) - 1][0];
for (int i = 0; i <= 9; i++) ans /= fact[cnt[i]];
printf("%d\n", ans);
}
return 0;
}