搜索 & 枚举
解法:搜索 & 枚举
因为好整数是 $k$ 回文整数的排列,因此我们可以把数字频率相同的 $k$ 回文整数视为同一种。枚举每种 $k$ 回文整数,再算算它不以 $0$ 为开头的排列有几种即可。
怎样枚举每种 $k$ 回文整数呢?由于回文数要求前半和后半相同,因此我们可以通过 DFS 搜索回文数的前半部分填什么。找到一个 $k$ 回文整数之后,再统计它的数字频率即可。这一部分的复杂度是 $\mathcal{O}(b^{\frac{n}{2}} \times b)$,其中 $b = 10$ 是可选的数字种类。因为 $n$ 很小所以没问题。
最后一个问题:给定每种数字的频率,怎么求不以 $0$ 为开头的排列有几种?我们可以用全排列数扣掉以 $0$ 为开头的排列。带重复元素的全排列数公式为
$$\frac{n!}{\prod n_i!}$$
其中 $n_i$ 是第 $i$ 种元素的出现频率。那么设 $c_i$ 为数字 $i$ 出现的频率,答案就是
$$
\frac{n!}{\prod\limits_{i = 0}^9 c_i!} - \frac{(n - 1)!}{(c_0 - 1)! \times \prod\limits_{i = 1}^9 c_i!}
$$
因为对于每种 $k$ 回文整数,我们需要 $\mathcal{O}(b)$ 的复杂度计算答案,这一部分的复杂度也是 $\mathcal{O}(b^{\frac{n}{2}} \times b)$。
参考代码(c++)
###cpp
class Solution {
public:
long long countGoodIntegers(int n, int K) {
long long P[n];
P[0] = 1;
for (int i = 1; i < n; i++) P[i] = P[i - 1] * 10;
int cnt[10] = {0};
// 用 string 保存每种数的出现次数,因为 vector 不能放进 unordered_set 里
unordered_set<string> st;
auto dfs = [&](auto &&self, int l, int r, long long now) {
if (l > r) {
// 所有数都填完了,检查能否被 K 整除,并记录数字出现频率
if (now % K != 0) return;
string s;
for (int i = 0; i < 10; i++) s.push_back(cnt[i]);
st.insert(s);
return;
}
// 枚举第 l 和 r 位放什么数,注意不能有前导 0
for (int i = (r == n - 1 ? 1 : 0); i < 10; i++) {
if (l == r) {
cnt[i]++;
self(self, l + 1, r - 1, now + i * P[l]);
cnt[i]--;
} else {
cnt[i] += 2;
self(self, l + 1, r - 1, now + i * (P[l] + P[r]));
cnt[i] -= 2;
}
}
};
dfs(dfs, 0, n - 1, 0);
// 预处理阶乘
long long fac[n + 1];
fac[0] = 1;
for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i;
long long ans = 0;
// 枚举每种 K 回文整数
for (auto &s : st) {
// 全排列数
long long a = fac[n];
for (int i = 0; i < 10; i++) a /= fac[s[i]];
ans += a;
if (s[0] == 0) continue;
// 减去以 0 为开头的排列数
a = fac[n - 1];
for (int i = 0; i < 10; i++) {
int t = (i == 0 ? s[i] - 1 : s[i]);
a /= fac[t];
}
ans -= a;
}
return ans;
}
};