D - Digits Parade

問題

atcoder.jp
以下では、最も大きな桁を1番目として考えてます。あとこの記事はかなり備忘録寄りになってます

考察

・ひと目みて桁DPだと気づいたよ。すっかり忘れていたのでこのサイトで復習した。
・余りが5である必要があるので、各桁について余りを管理する必要がある。大きい桁から計算するメモ化再帰を考えた。
・メモ配列 を 目の数字をにしたとき、13で割った余りがである場合の数と定義する。このとき、桁の重みの余り となる数とすると、更新式は以下の通り。

+=次の桁の数字

・イメージは、digit桁目にnumを使って余りがmodになるためには、次の桁以降の余りが nmod になっていなければならない。

・が?ならば0~9を試せば良い。桁の余りの重みも簡単に求めることができる。なので、順番に余りを求めていけば良い。コード中のbaseがそれに該当する
提出したコードはこれ
atcoder.jp

・実際は2次元でできる。必要なのは桁とmodだけの情報で良い。上記の提出でもnumはnmodを求める場合のみ用いている。
・上記のコードは関数呼び出し時に桁の数字を決める、下のコードは関数内でいま見ている桁をどうするか決める。
・感覚的にはdigit目の文字が'?'であれば、より多くのnmodを取る事ができる。例えば、digit桁目がn,uでもcmodの値がおなじ場合があるので。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
constexpr int MOD = 1000000007;

signed main(){
    string s; cin >> s;
    int N = s.size();
    auto memo = vectors( N + 2,13,-1LL);
    // 0-index
    vector<int>base(s.size() + 1,0LL);
    base[ N - 1] = 1;
    
    for(int i = N - 2; i >= 0; --i)
        base[i] = (9 * base[i + 1] + base[i + 1]) % 13;
    
    for(int i = 0; i < 13; ++i)
        memo[s.size() - 1][i] = (i <= 9 and (s.back() == '?' or s.back() - '0' == i) ? 1 : 0);
    
    
    function<int(int,int)>solver = [&](int digit,int cmod){
        if( memo[digit][cmod] != -1LL) return memo[digit][cmod];
        memo[digit][cmod] = 0;
        // digit桁目でcmodとなる場合の数を求める。　関数内で次の数字を決める。
        int idx = digit;
        //今見ている桁が'?'のとき、0~9をすべて試す
        if(s[idx] == '?'){
            for(int num = 0; num < 10; ++num){
                int temp =  ( base[digit] * num ) % 13;
                int nmod =  (cmod - temp <= 0 ? cmod - temp + 13 : cmod - temp) % 13;
                memo[digit][cmod] += solver(digit + 1,nmod);
                memo[digit][cmod] %= MOD;
            }
        } else {
            int num = s[idx] - '0';
            int temp =  ( base[digit] * num ) % 13;
            int nmod =  (cmod - temp <= 0 ? cmod - temp + 13 : cmod - temp) % 13;
            memo[digit][cmod] += solver(digit + 1, nmod);
            memo[digit][cmod] %= MOD;
        }
        return (memo[digit][cmod]) % MOD;
    };
    cout << (solver(0,5)) << endl;
}