TopCoder SRM 813 : Div1 Medium RaftingOnDunajec

うーん、時間かけすぎ。
https://community.topcoder.com/stat?c=problem_statement&pm=17161&rd=18868

問題

長さSの区間がある。
これをC個の部分区間で覆い切りたい。各区間の組み合わせは何通りか。

解法

各部分区間の取り方はO(S^2)個ある。
f(i,r,c) := i通り目の区間までの取り方を決めたとき、右端rまで覆われていて、そこまでにc個の割り当てがなされているときの組み合わせ
とすると、状態がO(S^3*C)、各状態から次の部分区間を取る個数がO(C)通りで、O(S^3*C^2)で解ける。
ただ、これだとTLEする。

そこで何とか状態を減らそう。
g(i,r,c) := i通り目の区間までの取り方を決めたとき、右端rまで覆われていて、そこまでにc個の『異なる』割り当てがなされているときの組み合わせ
とすると、各状態に対し、次の状態遷移はcが1つずつしか増えないのでO(S^3*C)となる。

部分区間の取り方をN個とすると、解はg(N,|S|,c)*h(C,c)の総和(h(x,y)は、x個のものを異なるy個の箱に、各箱1個以上のものが入るよう振り分ける分け方)となる。

ll mo=1000000007;

ll from[105][105];
ll to[105][105];


class RaftingOnDunajec {
	public:
	int count(int S, int C) {
		int i,j;
		ZERO(from);
		from[0][0]=1;
		int L,R,x;
		FOR(L,S) {
			for(R=L+1;R<=S;R++) {
				memmove(to,from,sizeof(from));
				for(int num=0;num<=99;num++) {
					for(x=L;x<=S;x++) {
						(to[max(R,x)][num+1]+=from[x][num])%=mo;
					}
				}
				swap(from,to);
			}
		}
		
		ll f[101]={};
		ll t[101]={};
		f[0]=1;
		ll fact[101]={};
		fact[0]=1;
		for(i=0;i<C;i++) {
			fact[i+1]=fact[i]*(i+1)%mo;
			ZERO(t);
			for(j=0;j<C;j++) {
				(t[j]+=f[j]*j)%=mo;
				(t[j+1]+=f[j])%=mo;
			}
			swap(f,t);
		}
		
		ll ret=0;
		for(i=1;i<=C;i++) {
			ret+=from[S][i]*f[i]%mo*fact[i]%mo;
		}
		return ret%mo;
	}
}

まとめ

最初ガッツリO(S^3*C^2)の解法を書いて、そのあと一端誤った高速化案に走ってしまい、解くのが遅れた。