AtCoder ARC #067 : E - Grouping

EもFもしょうもないミスでタイムロスしすぎてつらい。
http://arc067.contest.atcoder.jp/tasks/arc067_c

問題

互いに区別されるN人の人を、いくつかのグループに分ける。
各グループはA～B人のいずれかで構成され、かつあるi人のグループは0個かC～D個のいずれかでなければならない。
そのような組み合わせは何通りか。

解法

以下の状態を考え、f(A,N)を求めればよい。
f(p,q) := 残りq人をp人以上のグループで構成するときの組み合わせ

f(p,q)は以下の合計である。以下をメモ化再帰なりDPで求めよう。

• p人のグループを一つも作らない場合、
• p人のグループをx個作る場合、

int N,A,B,C,D;
ll mo=1000000007;
const int NUM_=400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];

ll memo[1010][1010];

ll combi(ll N_, ll C_) {
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

ll dfs(int a,int l) {
	int i;
	
	ll& ret=memo[a][l];
	if(ret>=0) return ret;
	
	ret=0;
	if(l==0) {
		ret = 1;
	}
	else {
		if(a>B) return 0;
		ret += dfs(a+1,l);
		ll v=1;
		for(i=1;i<=D && a<=l;i++) {
			(v *= combi(l,a) * inv[i] % mo)%=mo;
			l -= a;
			
			if(i>=C && i<=D) ret += v*dfs(a+1,l)%mo;
		}
	}
	ret%=mo;
	return ret;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A>>B>>C>>D;
	
	MINUS(memo);
	combi(1,1);
	
	cout<<dfs(A,N)<<endl;
	
}

まとめ

なんかARCはなかなかいい順位とれないなぁ。