Typical DP Contest E:数

問題文

http://tdpc.contest.atcoder.jp/tasks/tdpc_number

解法

桁DP.

Zig-Zag Numbersとかいう桁DPで解けるJOIの過去問があって,それの親戚の劣化版みたいな感じ.

dp[i][j][k]:i桁目まで決めて,j=(今までの合計)%Dで,k=(ここから先の桁を自由に決めていいか)(true or false)という状態になる通り数.

みたいなものをした.
自由に決めていいかというのは,「N=101のときに,1桁目を1と決めたら2桁目は0しか選べない」みたいな感じかどうか,ということです.

条件を満たす正の整数の個数を数え上げなければいけないけど,このアルゴリズムだと0も数えてしまうので最後に1引いた.

コード

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

const int mod=1e9+7;
int a[20000];
int N,D;

int dp[20000][2][100];

int calc(int keta,int jiyuu,int sum){
    if(keta==N)return (sum==0);
    if(~dp[keta][jiyuu][sum])return dp[keta][jiyuu][sum];
    int ret=0;

    for(int i=0;i<10;i++){
        if(jiyuu==0&&a[keta]<i)break;
        int val;
        val=calc(keta+1,jiyuu|(a[keta]!=i),(sum+i)%D);
        ret=(val+ret)%mod;
    }

    return dp[keta][jiyuu][sum]=ret;
}

int main(){
    string s;
    cin>>D>>s;
    N=s.size();
    for(int i=0;i<N;i++){
        a[i]=s[i]-'0';
    }
    fill_n(**dp,20000*2*100,-1);
    cout<<(calc(0,0,0)+mod-1)%mod<<endl;
    return 0;
}