Soxy Log

競技プログラミングに関すること

AtCoder ABC135 D - Digits Parade

問題


AtCoder ABC135 D - Digits Parade

解法


dp[i][j]を先頭i文字として考えられるもののうち,13で割ったあまりがjであるものの数と定義し、 動的計画法でdp[N][5]を求める。(解答)

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = pow(10,9) + 7;
 
string S;
int dp[100005][13];
 
ll solve(int pos, int rem) {
    if(pos == S.length()) return rem == 5;
    if(dp[pos][rem] != -1) return dp[pos][rem];
    ll ans(0);
    if(S[pos] == '?') {
        for(int i(0); i < 10; ++i) {
            ans += solve(pos + 1, (rem * 10 + i) % 13) % mod;
        }
    }
    else ans += solve(pos + 1, (rem * 10 + S[pos] - '0') % 13) % mod;
    return dp[pos][rem] = ans % mod;
}
 
int main() {
    memset(dp, -1, sizeof dp);
    cin >> S;
    cout << solve(0, 0) << endl;
}