题解 | #小红的01串（五）#

记忆化搜索： 如果不是'?'则正常取余否则就有两种情况?=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();
    }
}