[AtCoder] ABC135 D – Digits Parade (400点)
問題
一部が ? で与えられる数字の文字列 S について、13で割って5余る数で考えられる物は何通りあるか。
答えを 1e9+7 で割った余りで答えよ。
制約
- \(1 \leq |S| \leq 10^5\)
考え方
まずは単純に全探索することを考えて見ます。10の「?の数」乗 通りの数が考えられるので、それぞれに対して13で割って5余る数かを確かめていると、制限時間内に計算を終了することができません。
そこで、何らかの高速化が必要になります。今回のように、文字列で入力が与えられるような非常に桁数が大きい問題は「桁ごとに考える」とうまくいく場合があります。
1桁目から順に、何通りあるのかを考えていきます。
dp[i][j] := i 桁までの数として考えられる物のうち、余りが j となるのは何通りか
とすると、実は動的計画法で計算できることに気が付きます。配列の大きさは最大でも \(10^5 \times 13\) となるので、十分計算できる大きさです。
なぜ13で割るのか（なぜ13でなければならないのか）を考えてみると、動的計画法に気が付きやすいかもしれません。これが更に大きい値だと配列を確保できない場合があるからです。
解法
dp[i][k] := i 桁までの数として考えられる物のうち、余りが kとなるのは何通りか
として、動的計画法により更新していきます。( i は 0 始まり）
S[i]が ? でない時（数字 j の時）は、0桁目からi-1桁目までの数が決まっているとすると、\( j \cdot 10 ^ i\) だけ数が増加することになります。
つまり、元の数を13で割った余りを k とすると、余りは\(( k + j \cdot 10 ^ i )\%13\)になるはずです。
i-1桁目までの数で余りが k だったものは、全て余り\(( k + j \cdot 10 ^ i )\%13\)になるので、以下のように更新すれば良いことになります。
dp[i][\(( k + j \cdot 10 ^ i )\%13\)] += dp[i-1][k]
S[i]が ? の時は、j を0から9までに変化させて同様の更新を行えば良いです。
ソースコード
#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int INF = 2100100100;
const int MOD = 1e9 + 7;
int dp[110000][13];
int main() {
string S;
cin >> S;
int len = S.size();
reverse(S.begin(), S.end());
if (S[0] == '?') {
for (int i = 0; i < 10; i++) {
dp[0][i] = 1;
}
} else {
int index = S[0] - '0';
dp[0][index] = 1;
}
int num = 1;
for (int i = 1; i < len; i++) {
num *= 10;
num %= 13;
if (S[i] == '?') {
for (int j = 0; j < 10; j++) {
for (int k = 0; k < 13; k++) {
int index = (k + j * num) % 13;
dp[i][index] += dp[i - 1][k];
dp[i][index] %= MOD;
}
}
} else {
for (int k = 0; k < 13; k++) {
int j = (S[i] - '0');
int index = (k + j * num) % 13;
dp[i][index] += dp[i - 1][k];
dp[i][index] %= MOD;
}
}
}
cout << dp[len - 1][5] << endl;
return 0;
}