记忆化搜索: 如果不是'?'则正常取余否则就有两种情况?=0或者?=1的情况将两者情况的结果相加得到结果
import java.io.*;
import java.util.*;
public class Main {
static int mod=(int)(1e9+7);
public static void main(String[] args) {
char[] c=Str().toCharArray();
long[][] dp=new long[c.length+1][13];
for(long[] d:dp){
Arrays.fill(d,-1L);
}
long ans=dfs(c,dp,0,0L)%mod;
pw.println(ans);
pw.flush();
}
public static long dfs(char[] c,long[][] dp,int i,long x){
if(i==c.length) return x==0?1:0;
if(dp[i][(int)x%13]!=-1) return dp[i][(int)x%13];
long ans=0;
if(c[i]!='?'){
ans=dfs(c,dp,i+1,(x*10+c[i]-'0')%13)%mod;
}else{
for(int j=0;j<=1;j++){
ans=(ans+dfs(c,dp,i+1,(x*10+j)%13))%mod;
}
}
dp[i][(int)x%13]=ans;
return ans;
}
}
动态规划:通过记忆化推出转移方程
public class Main {
static int mod=(int)(1e9+7);
public static void main(String[] args) {
String str = Str();
char[] c = str.toCharArray();
long[][] dp = new long[c.length + 1][13];
dp[0][0] = 1;
for (int i = 0; i < c.length; i++) {
for (int j = 0; j < 13; j++) {
if (dp[i][j] != 0) {
if (c[i] != '?') {
int digit = c[i] - '0';
int newMod = (j * 10 + digit) % 13;
dp[i + 1][newMod] = (dp[i + 1][newMod] + dp[i][j]) % mod;
} else {
for (int digit = 0; digit <= 1; digit++) {
int newMod = (j * 10 + digit) % 13;
dp[i + 1][newMod] = (dp[i + 1][newMod] + dp[i][j]) % mod;
}
}
}
}
}
long ans = dp[c.length][0];
pw.println(ans);
pw.flush();
}
}