Typical DP Contest E:数
解法
桁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; }