关注公众号【算法码上来】，每日算法干货马上就来！
题目描述
感谢 kentln 供题，题目的出处已经不记得了，只能凭印象描述一下题意。
大致意思就是给你一个字符串 $s$ ，表示一个正整数，但是有些位已经模糊了（用 $x$ 表示）。现在知道它一定能被 $n$ 整除，求 $s$ 表示的正整数一共有多少种可能？注意，不允许出现前导 $0$ 。
示例1
输入：
8x4171x 5
输出：
20
解释：
第一个 x 可以取 0 到 9 一共 10 个数，第二个 x 只能取 0 或者 5 ，所以一共有 10 * 2 = 20 种可能。示例2
输入：
x9953xx 1
输出：
900
解释：
第一个 x 可以取 1 到 9 一共 9 个数，后面两个 x 随便取，所以一共有 9 * 10 * 10 = 900 种可能。提示
- $6 \le s.length \le 9$
- $1 \le n \le 100$
- 输入数据可能不止一组，请输入到文件结束为止
- 数据组数 $T = 10000$
题解
这题最暴力的方法就是枚举所有的数，然后判断每个数是否是 $n$ 倍数就行了，时间复杂度是 $O(10^{s.length} \cdot T)$ ，最大可以达到 $10^{13}$ 级别，无法接受！
那么我们从 $s$ 的最低位（也就是第 0 位）开始考虑，假设当前已经考虑到了第 $i$ 位。我们用数组 $c[k]$ 表示前面 $i-1$ 位表示的所有数字中余数为 $k$ 可能有几种，初始的时候 $c[0] = 1$ ，其它都为 $0$ （因为一位都没有的话，就当作 $0$ 处理）。
如果第 $i$ 位不是 $x$ ，那就说明第 $i$ 位上面已经有数字了。否则的话可以取 $0$ 到 $9$ 之间任意数（如果 $x$ 在最高位，排除掉 $0$）。
假设第 $i$ 位取 $j$ ，那么第 $i$ 位上面的数字在整个数字中的大小就是 $j \cdot 10^i$ 。假设它对 $n$ 取模结果是 $q = (j \cdot 10^i) \% n$ ，那么对于前 $i-1$ 位来说，余数为 $k$ 的答案有 $c[k]$ 种。加上第 $i$ 位之后，余数变成了 $(q+k)\%n$ ，所以前 $i$ 位余数为 $(q+k)\%n$ 的答案要加上 $c[k]$ 。
最后整个 $s$ 的可能情况种数就是 $c[0]$ 。
时间复杂度为 $O(s.length \cdot 10 \cdot n \cdot T)$ ，极限情况下会达到 $9 \cdot 10^{7}$ 级别，还可以接受。
代码
c++
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
int n;
while (cin >> s) {
cin >> n;
vector<int> c(n, 0);
c[0] = 1;
int pow = 1;
for (int i = s.size()-1; i >= 0; --i) {
int lb = 0, rb = 9;
if (s[i] != 'x') {
lb = rb = s[i] - '0';
} else if (!i) {
lb = 1;
}
vector<int> tc(n, 0);
for (int j = lb; j <= rb; ++j) {
int q = (j * pow) % n;
for (int k = 0; k < n; ++k) {
tc[(q+k)%n] += c[k];
}
}
c = tc;
pow *= 10;
}
cout << c[0] << endl;
}
return 0;
}评测
因为这题忘了出处了，所以评测的话得靠自己运行，然后和正确答案比较。
输入数据和标准输出在 公众号后台回复【kentln-0】 下载，步骤如下：
- 首先在你的 c++ 程序
main函数开头加上如下两句：
作用就是重定向输入输出，从freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);in.txt读入数据，输出答案到out.txt中。 - 编译你的 c++ 程序
g++ 代码文件名.cpp -o test，并运行./test。 - 然后比较你的输出和标准输出区别，采用命令
comp ans.txt out.txt。
