Algoogle

Algorithm for Programming Contest

Typical DP Contest E - 数

Category: TDPC Tag: dp

E - 数

問題概要


解法


len : Nの桁数
一番左の桁から数を0~9までまわしてそれまでの合計をDでmodとったものを保存していく.
dp[i][j][k] : 左からi桁目まででDでmodをとったものがjになる数. kは数がN未満かどうか.
数がN以上かは, 前の状態がN以上かつ, 回してる数字がNのその桁の数以上.
それらは基本的に無視するが, すべての桁が同じ場合は答えに含めるので,
例外として同じ数字の時はカウントしておく. (テストケース弱いのでカウントしなくても通りはする)
dp[len][0][1] + dp[len][0][0] - 1
が答えになる. -1は倍数として0もカウントしてるから.

コード


(E.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <string>
#define int long long
#define repi(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,a) repi(i,0,a)
using namespace std;
const int mod = 1000000007;

string N;
int D;
int dp[10010][100][2];

void input(){ cin >> D >> N;}

int solve(){
    int T = N.size();
    dp[0][0][0] = 1;
    rep(i,T) rep(j,D) rep(k,2) rep(d,10){
        if(k == 0 && d > N[i] - '0') break;
        int nj = (j + d) % D;
        int nk ;
        if(k == 0 && d < N[i] - '0') nk = 1;
        if(k == 0 && d >= N[i] - '0') nk = 0;
        if(k == 1) nk = 1;
        dp[i+1][nj][nk] += dp[i][j][k];
        dp[i+1][nj][nk] %= mod;
    }
    return (dp[T][0][1] - 1 + mod) % mod;
}

signed main(){
    input();
    cout << solve() << endl;
    return 0;
}

Comments