これ系の桁DPは苦手。
https://www.hackerrank.com/contests/eeic-programming-contest-0/challenges/count-zero-1-1
問題
F(n) := nの10進数表記で、leading zero以外に0が現れる桁数
とする。整数N,Pが与えられる。Pの倍数でN以下の正整数vについて、F(v)の総和を求めよ。
解法
N/Pが10^7以下ぐらいなら、vを総当たりすればよい。
N/Pがそれよりも多い場合、桁DPを考えよう。
vの各桁について、
- leading zero以外の0
- leading zeroまたは正の数
のどちらが来るかをbitdpで2^10程度総当たりし、桁DPでそのようなN以下のPの倍数を求めよう。
N/Pが10^7以上ということはPは100以下なので、Pで割った余りの情報もDPの状態で持ち越すようにする。
ll N,P; int mask; ll p10[11]; ll dp[11][2][2][100]; ll hoge(int d,int le,int po,int m) { if(d==-1) { return m==0 && po; } if(dp[d][le][po][m]>=0) return dp[d][le][po][m]; ll pat=0; int x=N/p10[d]%10; if(mask&(1<<d)) { if(po) pat=hoge(d-1,le | (x>0),po,m*10%P); } else { int i; for(i=1;i<=9;i++) { if(le==0 && i>x) continue; pat+=hoge(d-1,le | (i<x),1,(m*10+i)%P); } if(po==0) { pat+=hoge(d-1,le | (0<x),po,(m*10+0)%P); } } return dp[d][le][po][m]=pat; } int hoge(ll v) { int ret=0; while(v) { ret+=v%10==0; v/=10; } return ret; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>P; p10[0]=1; FOR(i,10) p10[i+1]=p10[i]*10; ll ret=0; if(N/P<=100000000LL) { for(ll a=P;a<=N;a+=P) ret+=hoge(a); } else { for(mask=1;mask<1<<10;mask++) { MINUS(dp); ret+=__builtin_popcount(mask)*hoge(10,0,0,0); } } cout<<ret<<endl; }
まとめ
手間ではあるけどCよりは気楽かな…。