Interesting DP problem from AC

Digit_parade.md

Interesting problem on dynamic programming from atcoder. Given a string in the format "(|?)+" find how many number can be formed such that the reminder of the division of each of this numbers by 13 gives exactly 5.

So lets define function dp[x][y] to be count of such numbers for prefix of length x and reminder y. For example, for 1?2 dp[2][5] will mean the count of such numbers for substring 1? and the reminder 5.

The interesting part is the transition. It uses implicit difinition.

for (all prevReminder)
  dp[i+1][ (prevReminder * 10 + curDigit)%13 ] += dp[i][prevReminder]

#include <bits/stdc++.h>
using namespace std;
const size_t M = 1e9 + 7;

int main(int,char**) {
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    string s;
    cin >> s;
    
    int n = s.size();
    
    // dp(x, y) = how many such numbers
    // where x is the prefix length, y is reminder by 13
    vector< vector<size_t> > dp(n+1, vector<size_t>(13, 0));
    dp[0][0] = 1;
    
    
    for (int i = 0; i < n; ++i) {
        if (s[i] != '?') {
            int curDigit = s[i] - '0';
            for (int prevRem = 0; prevRem < 13; ++prevRem) {
                int curRem = (10*prevRem + curDigit)%13;
                dp[i+1][curRem] = (dp[i+1][curRem] + dp[i][prevRem])%M;
            }
        } else {
            // curDigit may be any 0..9
            for (int curDigit = 0; curDigit < 10; ++curDigit) {
                for (int prevRem = 0; prevRem < 13; ++prevRem) {
                    int curRem = (10*prevRem + curDigit)%13;
                    dp[i+1][curRem] = (dp[i+1][curRem] + dp[i][prevRem])%M;
                }
            }
        }
    }
    cout << dp[n][5] << endl;
    return 0;
}