原题链接

昨天做的时候压根没往dp这个方向去想,一直在和数论死磕.

今天重新想了下,其实也没有一开始想的那么难,所以做任何题都要找对解题的方向啊。

题意很简单就不翻译了.

主要说一下解题思路.

首先是dp[][]

第一维i表示当前长度,所以范围显而易见 [0,len-1] (len为字符串长度)
第二维j表示%13的余数,范围也显而易见 [0,12]

对于当前s[i] != '?' 的情况,很好判断,只需要原来的数*10+s[i]即可

如果当前s[i]=='?', 我们只需要开一个 [0,9] 的循环枚举,接下来的处理方式同上

代码如下

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define rg register
#define maxn 150000
const ll mod=1e9+7;
string s;
int dp[maxn][15];
int main()
{
    cin>>s;
    int len=s.length();
    dp[0][0]=1;
    for(rg int i=0;i<len;++i)
    {
        if(s[i]!='?')//对于不是问号的地方,只需要把之前的数*10+这个数就行了 
        {
            for(rg int j=0;j<=12;++j)
            {
                dp[i+1][(j*10+s[i]-'0')%13]=dp[i][j];
            }
        }
        else//对于是问号的地方,也只是需要多开个循环枚举问号中可能的数字,然后处理方式与上面相同 
        {
            for(rg int j=0;j<=9;++j)
            {
                for(rg int k=0;k<=12;++k)
                {
                    dp[i+1][(j+k*10)%13]=(dp[i+1][(j+k*10)%13]+dp[i][k])%mod;
                }
            }
        }
    }
    cout<<dp[len][5];//因为最后是%13==5 所以第二维为5 
}