算法
(状压DP) $O(t \cdot 2^n \cdot d \cdot n)$
记 f[sta][p]
表示已经使用的数字的状态为 sta
,现在数字模 d
的结果为 p
,每次找到 $sta$ 里面还没放进去的一个数字,然后放进去,$p = p * 10 + x$,取模后更新即可。
不过这个题问的是最后有多少种方案,是考虑顺序的。相同元素顺序被重复计数了,所以要记得除掉对应元素个数的阶乘。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::string;
using std::vector;
int f[1<<12][1010];
int main() {
int t;
cin >> t;
while (t--) {
std::memset(f, 0, sizeof f);
string s;
cin >> s;
int n = s.size();
int d;
cin >> d;
vector<int> a(n);
rep(i, n) a[i] = s[i] - '0';
vector<int> cnt(10);
rep(i, n) cnt[a[i]]++;
int n2 = 1 << n;
f[0][0] = 1;
rep(i, n2) {
rep(j, d) {
if (f[i][j]) {
rep(k, n) {
if ((i & (1<<k)) == 0) {
f[i | (1<<k)][(j * 10 + a[k]) % d] += f[i][j];
}
}
}
}
}
int ans = f[n2 - 1][0];
rep(i, 10) {
while (cnt[i] > 1) {
ans /= cnt[i];
--cnt[i];
}
}
cout << ans << '\n';
}
return 0;
}