洛谷P4163 [SCOI2007] 排列
题意
给一个数字串 \(s\) 和正整数 \(d\), 统计 \(s\) 有多少种不同的排列能被 \(d\) 整除（可以有前导 \(0\)）。
思路
考虑状压dp。
\(dp_{S,k}\) 表示当前已经选定了 \(S\) 集合（下标）的数，模 \(d=k\) 的方案数。
状态转移方程：
\[dp_{S|2^j,(k\times10+s_j)\bmod d} \mathrel{+}=dp_{S,k} \]需要注意如果有数字出现了多次，会计算重复。
若一个数出现了 \(c\) 次，答案除以 \(c!\) 即可。
时间复杂度：\(O(Tn2^nd)\)。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int dp[1 << 11][1005];
int fac[15];
signed main() {
int T; cin >> T;
string S; int d;
fac[0] = 1;
for (int i = 1; i <= 10; i ++) fac[i] = fac[i - 1] * i;
while (T --) {
memset(dp, 0, sizeof(dp));
cin >> S >> d;
dp[0][0] = 1;
for (int i = 0; i < (1 << S.size()); i ++) {
for (int j = 0; j < S.size(); j ++) {
if (i >> j & 1) continue;
for (int k = 0; k < d; k ++) {
dp[i | (1 << j)][(k * 10 + S[j] - '0') % d] += dp[i][k];
}
}
}
int ans = dp[(1 << S.size()) - 1][0];
for (int i = 0; i <= 9; i ++) {
int c = 0;
for (auto x : S) {
if (x == i + '0') c ++;
}
ans /= fac[c]; // 除去重复
}
cout << ans << "\n";
}
return 0;
}