桁和の桁和 [yukicoder 1085]

https://yukicoder.me/problems/no/1085

前提知識

• 数字根（知っていれば早い）
• 動的計画法

解説

https://yukicoder.me/submissions/500381

数字根を知らないとかなり時間をロスすると思う。
ある数について桁和を取れるだけとった結果を数字根という。
数字根は元の数のmod 9と等しくなることが知られている。
ただし、mod 9で0の場合は0以外なら9である。
この性質を計算でチェックサムとして用いる（検算方法として用いる）九去法というのもある。

ここまで分かっていれば、?をある数に変えたときの数 mod 9がDである組合せを求めればいいことが分かる。
今回は数字根なので、?をある数に変えて一回桁和を取ったときの数 mod 9がDである組合せを求めても同じであり、
こちらの方がやや簡単にDPがかける。
dp[i][mo] := i桁目まで確定していて、今までの桁和mod9がmoである組合せ
?だったら[0,9]で全通り試せばいいし、そうでないなら、それで確定。

コーナーケースが問題で、例えば、T=??????, D=9の場合。
D=9の時はmod9で0の組合せが最終的な答えとなるが、S=000000も数え上げられてしまう。
なので、全部0のSが作成可能で、D=9の時は答えが1つ減るので注意。

あとは、D=0となるのはSが全部0の時だけなので、
別途計算して答えてやろう。

string T; int D;
mint dp[101010][9];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> T >> D;

    bool canAllZero = true;
    fore(x, T) if (x != '?' && x != '0') canAllZero = false;

    if (D == 0) {
        if (canAllZero) cout << 1 << endl;
        else cout << 0 << endl;
        return;
    }

    int N = T.size();

    dp[0][0] = 1;
    rep(i, 0, N) rep(mo, 0, 9) {
        if (T[i] == '?') {
            rep(nxt, 0, 10) dp[i + 1][(mo + nxt) % 9] += dp[i][mo];
        }
        else {
            dp[i + 1][(mo + T[i] - '0') % 9] += dp[i][mo];
        }
    }

    D %= 9;
    if (D == 0 && canAllZero) dp[N][D] -= 1;
    cout << dp[N][D] << endl;
}