Solution
首先看到
\(1\le |S|\le 10^5\)
考虑 DP。
定义 \(f_{i,j}\) 表示前 \(i\) 个位置的数除以 \(13\) 的余数为 \(j\)。
则有
-
当 \(s_i = ?\) 时，枚举余数 \(j\)(\(0\le j\le 12\)) 和当前选的数 \(k\)(\(0\le k\le 9\))。则有 \(f_{i,j*10+k}=f_{i,j*10+k}+f_{i-1,j}\)。
-
当 \(s_i \neq ?\) 时，同样枚举余数 \(j\)(\(0\le j\le 12\))。则有 \(f_{i,j*10+t}=f_{i,j*10+t}+f_{i-1,j}\)（其中 \(t\) 表示 \(s_i\) 转换成数字的数）。
Code
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 5;
const int M = 1e1 + 5;
const int mod = 1e9 + 7;
int n, f[N][M];
char s[N];
#define t (s[i] - '0')
signed main() {
cin >> (s + 1);
n = strlen(s + 1);
f[0][0] = 1;
for (int i = 1; i <= n; ++i)
for (int j = 0; j < 13; ++j) {
if (s[i] == '?') {
for (int k = 0; k <= 9; ++k) {
int now = (j * 10 + k) % 13;
f[i][now] += f[i - 1][j];
f[i][now] %= mod;
}
}
else {
int now = (j * 10 + t) % 13;
f[i][now] += f[i - 1][j];
f[i][now] %= mod;
}
}
cout << f[n][5];
return 0;
}