小红的01串（五）

参考牛客官方题解视频思路(https://www.bilibili.com/video/BV1fHBjYjEqq)

题意

给定一个01串，但其中有一些被'?'字符代替。 希望将'?'替换成'0'或者'1'字符，使得该串表示的正整数是13的倍数。求出有多少种方案（需要对1e9+7取模）

思路

首先需要观察到 13 这个常数较小 。

题目中 使得表示的正整数是 13 的倍数，即为该正整数 %13 为 0

根据取模运算的规律（？？），我们得到

(x*10)%13 == (x%13)*10%13 
(x*10+1)%13 == ((x%13)*10+1)%13

也就是说，只需要得到前 i 位数的余数，和当前位的个位数，就可以求得余数结果。而不需要知道前 i 位数具体是什么。换句话说，前 i 位余数相同的情况可以一并处理。这为我们使用动态规划快速求得答案提供基础。

所以可以得到以下的转移规律：

//dp[i][j] 代表前 i 位数 %13 时，余数为 j 的方案数 
dp[i-1][j] -> dp[i][k] 
k = j*10%13 (str[i] = 0) 
k = (j*10+1) %13 (str[i] = 1)

从前往后推，可以依次推出方案数。

代码

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
#define int long long
//观察到13这个常数较小
//表示的正整数是13的倍数，即为该正整数%13为0
//因为 (x*10)%13 == (x%13)*10%13
// (x*10+1)%13 == ((x%13)*10+1)%13
//所以dp[i-1][j] -> dp[i][k]
//k = j*10%13(str[i] = 0)
//k = (j*10+1)%13(str[i] = 1)
//dpij代表前i位数，%13时余数为j的方案数
signed main()
{
    string str;
    cin>>str;
    vector<vector<int>>dp(str.length(), vector<int>(13, 0));
    //cout<<str.length()<<'\n';
    int k;
    dp[0][1] = 1;
    int len = str.length();
    for(int i = 1; i<len; i++)
    {
        for(int j = 0; j<=12; j++)
    {
        if(str[i] == '0'||str[i]=='?')
        {
            k = (j)*10%13;
            dp[i][k] = (dp[i-1][j] + dp[i][k]) % mod;
        }
        if(str[i] == '1'||str[i]=='?')
        {
            k = (j*10+1)%13;
            dp[i][k] = (dp[i-1][j] + dp[i][k]) % mod;
        }
    }
    }
//     for(int i = 0; i<=len-1; i++)
//     {
//         for(int j = 0; j<=12; j++)
//     {
//         cout<<dp[i][j]<<' ';
//     }
//         cout<<'\n';
//     }
    cout<<dp[len-1][0];
    return 0;
}