给一个数字串 $s$ 和正整数 $d$, 统计 $s$ 有多少种不同的排列能被 $d$ 整除 (可以有前导 $0$)。
例如 $123434$ 有 $90$ 种排列能被 $2$ 整除，其中末位为 $2$ 的有 $30$ 种，末位为 $4$ 的有 $60$ 种。
第一行包含一个正整数 $T$ ($T \leq 15)$，表示测试数据的个数。
每组数据共一行，包含一个字符串 $s$ 和正整数 $d$ ($|s| \leq 10, d \leq 1000$)，中间用空格隔开。$s$ 保证只包含数字 $0, 1, 2, 3, 4, 5, 6, 7, 8, 9$。
对于每组数据，输出一行一个整数，表示能被 $d$ 整除的排列的个数。
由于 $|s| \leq 10$，因此可以考虑暴力枚举所有的排列，计算哪些可以整除的，其中暴力枚举可以用 dfs() 或者 next_permutation() 等等，时间复杂度为 $O \left( |s|! \right)$。
虽然能过，但是它的复杂度还是比较大的，比如 $|s| = 15$ 时可能就吃不消了。
由于字符串给的字符不是很多，于是这道题就可以进行状态压缩 DP 进行优化。
将原字符串中的字符看作一个可重集，记 $f_{A, j}$ 代表了使用集合 $A$ ($A \subseteq \mathrm{set}(s)$) 中的数字，目前模 $d$ 的值为 $j$，($|A|$ 个数) 排列的方案数。那么，使用刷表法，枚举下一个数是 $k$ ($k \notin A$)，那么就有 $$ \Large f_{A \cup \{k\}, (10j + k) \bmod d} \uparrow f_{i, j} $$
其中 $a \uparrow b$ 代表 a += b。
当然，最终状态应该是 $F = f_{\mathrm{set}(s), 0}$，但是这样可能会有重复 (是有序排列)，比如说两个 $0$，它就会被算两次——先枚举左边的 $0$，再枚举右边的 $0$ 和先枚举右边的 $0$，再枚举左边的 $0$。
像推导组合数一样，可以发现，每个数的重复是独立的。且如果这个数出现了 $i$ 次，那么它就会被重复计算 (共) $i!$ 遍。因此，我们只需要预处理出 $0 \sim 9$ 中每个数出现的次数，最后让 $F$ 分别除以它们的阶乘即为答案 (其实暴力也要这样的哦)，总时间复杂度 $O \left( 2^{|s|} d \right)$。
#include <bits/stdc++.h>
#define N 12
#define N2 2068
#define D 1034
using namespace std;
const int fact[11] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800};
int n, n2, d;
int i, j, k, ni, nj;
char s[N], *p;
int cnt[N];
int f[N2][D], ans;
int main(){
int T;
for(scanf("%d", &T); T; --T){
scanf("%s%d", s, &d);
memset(cnt, 0, sizeof cnt);
memset(f, 0, sizeof f);
for(p = s; *p; ++p) ++cnt[*p &= 15];
n2 = 1 << (n = p - s);
f[0][0] = 1;
for(i = 0; i < n2; ++i)
for(j = 0; j < d; ++j)
if(f[i][j])
for(k = 0; k < n; ++k)
if((ni = i | 1 << k) != i){
nj = (j * 10 + s[k]) % d;
f[ni][nj] += f[i][j];
}
for(j = 1, i = 0; i < 10; ++i) j *= fact[cnt[i]];
printf("%d\n", f[n2 - 1][0] / j);
}
return 0;
}
坑1：注意数组清零不要忘记，当然阶乘也可以事先预处理出来。