Given is a string SS. Each character in SS is either a digit (0, ..., 9) or ?.
Among the integers obtained by replacing each occurrence of ? with a digit, how many have a remainder of 55 when divided by 1313? An integer may begin with 00.
Since the answer can be enormous, print the count modulo 109+7109+7.
Constraints
SS is a string consisting of digits (0, ..., 9) and ?.
1≤|S|≤1051≤|S|≤105
Input
Input is given from Standard Input in the following format:
SS
Output
Print the number of integers satisfying the condition, modulo 109+7109+7.
??2??5
768
?44
1
7?4
0
?6?42???8??2??06243????9??3???7258??5??7???????774????4?1??17???9?5?70???76???
153716888
题意:给你一个字符串,字符串的内容只包含0-9和字符?,其中?代表你可以填写0-9中的任意一个,字符串中已经填写0-9的不能更该。问该字符串有多少种填法,是除与13余5 %13 = 5
dp[i][j] 表示前1-i位置中余数为j的方案数
#include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 5; const int mod = 1e9 + 7; int dp[maxn][13]; char str[maxn]; int main() { scanf("%s", str + 1); int n = strlen(str + 1); if (str[1] == '?') { for (int i = 0; i <= 9; i++) { dp[1][i] = 1; } } else { dp[1][str[1] - '0'] = 1; } for (int i = 2; i <= n; i++) { if (str[i] == '?') { for (int j = 0; j <= 9; j++) { //当前位置 for (int k = 0; k <= 12; k++) { //上一个位置 int t = (k * 10 + j) % 13; dp[i][t] = (dp[i][t] + dp[i - 1][k]) % mod; } } } else { for (int k = 0; k <= 12; k++) { int t = (k * 10 + (str[i] - '0')) % 13; dp[i][t] = (dp[i][t] + dp[i - 1][k]) % mod; } } } printf("%d\n", dp[n][5]); return 0; }