TopCoder SRM 669 Div1 Hard PowerPartition

うーむ、950ptはまだ自力で解くには結構きつい。
http://community.topcoder.com/stat?c=problem_statement&pm=13945

問題

この国の貨幣の各種類は、1,M,M^2,M^3....とM倍ずつ価値が増していく。
これらの貨幣を用いてXだけ支払いをするような貨幣の組み合わせは何通りあるか。

解法

Editorialを見て回答。
基本的にはXをM進数と見なし、下の桁からXに合うような組み合わせを決めていく。

F(n,b,a) := (b*(M^n)の金額を1～(M^a)の貨幣で払う払い方の組み合わせ。ただし価値1の貨幣は必ず使う) とする。
F(0,b,a)=1は明らか。

F(n,b,a)を考えるとき、すでに(b-1)*(M^n)の金額を払っている状態で、残り(M^n)を追加するとする。
(M^n)の金額を足す場合、(M^i)以上の貨幣だけを使うとする。残りの(b-1)*(M^n)は(M^i)以下の貨幣で払うと考える。
(すなわち、計(M^n)をb回払うと考え、前半ほど高い価値の貨幣で支払う)
そう考えると、で計算できる。
ただしb=1の時は、M*(M^(n-1))と考えて自同様に処理する。

次に、G(n,b,a) := (M進数において下からn桁目未満はXと一致しており、n桁目はbであるような金額を、1～(M^a)の貨幣で払う払い方の組み合わせ。こちらは1の貨幣を使わなくても良い)とする。
こちらも同様に(M^n)ずつ貨幣を追加することを考えるとで計算できる。

ll F[61][1000][61];
ll G[61][1000][61];
ll mo=1000000007;
int D[61];

class PowerPartition {
	public:
	int count(int M, long long X) {
		int dig=0;
		ZERO(F);
		ZERO(G);
		ZERO(D);
		
		while(X) D[dig++] = X % M, X /= M;
		
		int n,b,a,i;
		FOR(b,M) FOR(a,dig) F[0][b][a]=G[0][b][a]=1;
		for(n=1;n<dig;n++) for(b=1;b<=M;b++) FOR(a,dig) {
			ll& ne = F[n][b][a];
			if(b==1) FOR(i,min(n-1,a)+1) ne += F[n-1-i][1][a-i]*F[n-1][M-1][i] % mo;
			else FOR(i,min(n,a)+1) ne += F[n-i][1][a-i]*F[n][b-1][i] % mo;
			ne %= mo;
		}
		
		for(n=1;n<dig;n++) FOR(b,D[n]+1) FOR(a,dig) {
			ll& ne = G[n][b][a];
			if(b==0) ne = G[n-1][D[n-1]][a];
			else FOR(i,min(n,a)+1) ne += F[n-i][1][a-i]*G[n][b-1][i] % mo;
			ne %= mo;
		}
		
		return G[dig-1][D[dig-1]][dig-1];
	}
}

まとめ

yukicoderの貯金箱系問題の要領で解けるかなと思ったけどちょっと違った。