ABC135 D - Digits Parade

Last updated Apr 13, 2022

Editorial
Fps

最初に$S$を反転させておきます。

$$ f_{i} = \begin{cases} x^{10^i a} & (S_i=a) \\\ \sum_{j=0}^{9} x^{10^i j} & (S_i=?) \end{cases} $$

とすれば、$\prod_{i = 1}^{N} f_i$を$x^{13}=1$としたときの$x^5$の係数が答えになります。毎回周期13で集約すれば、$O(13^2 |S|)$です。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
string S;
cin >> S;
reverse(all(S));
i64 N = S.size();
vector<fp> dp(13);
dp[0] = 1;
i64 ten = 1;
rep(i,0,N) {
  vector<fp> nxt(13);
  if(S[i] == '?') {
    rep(j,0,13) {
      rep(k,0,10) {
        nxt[(j + k * ten) % 13] += dp[j];
      }
    }
  }
  else {
    i64 k = S[i] - '0';
    rep(j,0,13) {
      nxt[(j + k * ten) % 13] += dp[j];
    }
  }
  ten *= 10;
  ten %= 13;
  swap(nxt, dp);
}
cout << dp[5] << endl;