202120221 BUCT ACM集训队每周程序设计竞赛（8） 问题D :一月忘干净

2021-2022-1 ACM集训队每周程序设计竞赛（8） - 问题D :一月忘干净

• 题意：一个含有\(?\)和数字的字符串，\(?\)可以用\(0\)~\(9\)来代替，问你最后得到的数有多少个除以\(13\)余\(5\)

• 题解：首先要知道在取模意义下，乘法和加法都是能直接算的，设\(dp[i][j]\)为在第\(i\)个位置，余数为\(j\)的方案数，根据当前的\(s[i]\)算出当前的余数从上一个状态转移过来就好了

• 代码：

  #include <bits/stdc++.h>
  
  using namespace std;
  const int N=1e6+10;
  const int mod=1e9+7;
  #define ll long long
  #define pb push_back
  
  int n;
  char s[N];
  ll dp[N][20];
  
  int main(){
      scanf("%s",s+1);
  
      n=strlen(s+1);
      dp[0][0]=1;
      for(int i=1;i<=n;++i){
          if(s[i]=='?'){
              for(int k=0;k<10;++k){
                  for(int j=0;j<13;++j){
                      dp[i][(j*10+k)%13]=(dp[i][(j*10+k)%13]+dp[i-1][j])%mod;
                  }
              }
          }
          else{
              for(int j=0;j<13;++j){
                  dp[i][(j*10+s[i]-'0')%13]=(dp[i][(j*10+s[i]-'0')%13]+dp[i-1][j])%mod;
              }
          }
      }
  
      printf("%lld\n",dp[n][5]);
  
      return 0;
  }