ABC135D Digit Parade

問題

D - Digits Parade

？が混じったN桁の数（N<=10^5）を１３で割った余りが５になるものが何通りあるかをあるかという問題です。

考察

i番目までの数で13で割った余りがjのものの数をdp[i][j]としてDPを回します。
?の場合は０～９までを入れて回します。

１桁目（i=0)のところを工夫しました。

提出コード

#include <bits/stdc++.h>
using namespace std;

static const long long MOD=1000000007;
long long dp[100010][13];

int main(){
  string S;
  cin>>S;
  int len=S.length();
  for(int i=0;i<len;i++){
    if(i == 0){
      if(S.at(i)=='?'){
        for(int k=0;k<10;k++){
          dp[i][k]=1;
        }
      }
      else{
        dp[i][S.at(i)-'0']=1;
      }
      continue;
    }
    if(S.at(i)=='?'){
      for(int j=0;j<13;j++){
        for(int k=0;k<10;k++){
          long long temp=dp[i-1][j];
          dp[i][(j*10+k)%13]+=temp;
          dp[i][(j*10+k)%13]%=MOD;
        }
      }
    }
    else{
      for(int j=0;j<13;j++){
        long long temp=dp[i-1][j];
        dp[i][(j*10+S.at(i)-'0')%13]+=temp;
        dp[i][(j*10+S.at(i)-'0')%13]%=MOD;
      }
    }
  }
  cout<<dp[len-1][5]<<endl;
  return 0;
}