よくある桁DPとはまた違うけれど、あまりを状態にもつ DP を試せる問題ですね！

問題概要

"013?42???2??"
のような、'?' と数値で構成された、長さ $N$ の文字列が与えられる。

この '?' を埋めて数値を作る方法のうち、13 で割ったあまりが 5 になるようなものが何通りあるか、1000000007 で割ったあまりを求めよ。

ただし、先頭に 0 があっても、それを整数とみなすこととする。

制約

$1 \le N \le 10^{5}$

考えたこと

この問題、「先頭に 0 があったらダメ」とかだったら、ちょっと面倒になるけど、それがないので助かる ^^;

さて、整数を扱う一つの方法として「10 倍して〜を足すのを繰り返したものとみなす」というのがある！！！！

この考え方は、

桁DPな問題全般
AtCoder ABC 077 D - Small Multiple

あたりで見られる。たとえば、3141 とかだと、

0 からスタートする
10 倍する (0 になる)
3 を足す (3 になる)
10 倍する (30 になる)
1 を足す (31 になる)
10 倍する (310 になる)
4 を足す (314 になる)
10 倍する (3140 になる)
1 を足す (3141 になる)

という風にして構成できる！！！ざっくり

0 -> 3 -> 31 -> 314 -> 3141

という流れだ。今回みたいに「整数の各桁をどうするか」みたいな問題では、上記の見方が役に立つことが結構ある！

DP へ

以上のことを意識して、こんな感じの DP を組んでみよう。

dp[ i ][ j ] := S の上から i 桁目までを考えたときの、それを 13 で割ったあまりが j になるように、'?' を埋める方法の数

このとき、i から i+1 への遷移は次のように考えることができる！dp[ i ][ j ] に属する整数を 10 倍して x を足すと、それを 13 で割ったあまりは

(10 × j + x) % 13

になることに注意すると、遷移は次のように書ける！！

S[ i ] が 'x' または '?' のとき、

dp[ i + 1 ][ (10 × j + x) % 13 ] += dp[ i ][ j ]

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

const int MOD = 1000000007;
void add(long long &a, long long b) {
    a += b;
    if (a >= MOD) a -= MOD;
}
int main() {
    string S;
    cin >> S;
    vector<vector<long long>> dp(S.size()+1, vector<long long>(13, 0));
    dp[0][0] = 1;
    for (int i = 0; i < S.size(); ++i) {
        for (int j = 0; j < 13; ++j) {
            if (S[i] == '?') {
                for (int k = 0; k < 10; ++k) {
                    add(dp[i+1][(j*10+k)%13], dp[i][j]);
                }
            }
            else {
                int k = S[i] - '0';
                add(dp[i+1][(j*10+k)%13], dp[i][j]);
            }
        }
    }
    cout << dp[S.size()][5] << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 135 D - Digits Parade (水色, 400 点)

問題概要

制約

考えたこと

DP へ