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;
	}
};