SRM 358 Div2 Hard SameDigits
問題
f(x)を、xの連続する同一の数字のうち、最大の長さをLとしたとき、f(x)=Lとする。
(たとえばf(9111234)だったら111の3)
n桁以下のxで、f(x)がちょうどkになるものの個数をmod 44444444で求めよ。
制約条件
n,k ≦ 1000
方針
dp[i][j][h]を、
長さがi桁で、末尾j桁が同じ数が連続してて、これまでの同一数字の最大連続数が
h=0ならk未満、h=1ならちょうどk, h=2ならkより大であるような数の個数とする。
ソースコード
int dp[1001][1001][3]; class SameDigits { public: int howMany(int n, int k) { rep(i,n+1)rep(j,n+1)rep(h,3)dp[i][j][h]=0; dp[1][1][k==1]=9; for(int i=1;i<n;i++)for(int j=1;j<=i;j++){ //次に違う数 rep(h,3)(dp[i+1][1][h]+=dp[i][j][h]*9)%=mod; //次に同じ数 if(j==k-1){ (dp[i+1][k][1]+=dp[i][j][0]+dp[i][j][1])%=mod; (dp[i+1][k][2]+=dp[i][j][2])%=mod; } else if(j==k){ (dp[i+1][j+1][2]+=dp[i][j][1]+dp[i][j][2])%=mod; } else rep(h,3)(dp[i+1][j+1][h]+=dp[i][j][h])%=mod; } int ans=0; for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)(ans+=dp[i][j][1])%=mod; return ans; } };