TopCoder SRM 431 Div1 Medium MegaCoolNumbers

問題

power Aのcool numberを以下のような数と定義する。
数字を連続するA個に区切って、
それぞれの区間において、一つ一つの桁の数字が等差数列になっているようにすることができる。

power Aのmega cool numberとは
各桁の数字が非減少列になっていて、
power Aのcool numberになっていて、poewr A - 1のcool numberになっていない数のことを言う。

N桁のpower Aのmega cool numberの個数を
mod 10^9 + 7で求めよ。

制約条件

N, A≦1000

方針

Aがあまりに大きいと、同じ数のみが連続した2つの区間が出来てしまう。
この区間はつなげることができるので、A - 1のcool numberになってしまう。

このためAは30以下程度を考えればいい。
power Aのmega cool numberをDPにより求める。
dp[pos][group][prev][diff][flag]を、
pos桁目まで見たときにグループ数がgroup個で、直前の数字がprevであり、
現在の数列の公差がdiffであり、
flag = 0なら現在2項目以降であり、
flag = 1なら現在1項目であるような場合の数とする。

ここから次の数字を更新していくようなDPをすればいい。
次の数字は、現在のグループの仲間に入れるか、
新しいグループの先頭の数とするか。

新しいグループの先頭にするときは、現在のグループの末尾に加えられる数だと、
そのパターンを重複して数えることになるので、末尾に加えられない数のみを考える。

最後の1桁は公差を9通り考えてしまうと重複するので、公差は1通りしか考えないようにする。

ソースコード

const int mod = (int)1e9 + 7;

ll dp[2][50][10][10][2];

class MegaCoolNumbers {
  public:
  int count(int N, int A) {
		int mx = min(A, 30);
		int cur = 0, next = 1;
		memset(dp[cur], 0, sizeof(dp[cur]));
		dp[cur][0][0][0][1] = 1;
		
		rep(i, N){
			memset(dp[next], 0, sizeof(dp[next]));
			rep(j, mx + 1) rep(k, 10) rep(l, 10) rep(m, 2) if(dp[cur][j][k][l][m]){
				if(i && k + l < 10){
					(dp[next][j][k + l][l][1] += dp[cur][j][k][l][m]) %= mod;
				}
				if(j < mx && m) for(int nk = k; nk < 10; nk++) rep(nl, 10){
					if(nk == k + l) continue;
					if(i == N - 1 && nl) continue;
					(dp[next][j + 1][nk][nl][0] += dp[cur][j][k][l][m]) %= mod;
				}
			}
			swap(cur, next);
		}
		ll ans = 0;
		if(A < 30) rep(i, 10) rep(j, 10) rep(k, 2){
			(ans += dp[cur][A][i][j][k]) %= mod;
		}
		return ans;
  }
};