TopCoder SRM 826 : Div1 Hard SpaceMission

まーたしょうもないミスで落とした。
https://community.topcoder.com/stat?c=problem_statement&pm=17483&rd=19128

問題

N個の国の人で1つのチームを組む。
各国、出せる人数の最小値と最大値、あと偶奇が与えられる。
加えて、チーム全体の人数の最小値最大値が与えられる。

条件を満たすチーム編成は何通りか。

解法

まず各チーム(偶奇を考慮しつつ)最少人数をチームに組み込み確定させよう。
これで各国の最小値は以後無視してよくなる。
以後、2人組を各国何組追加するかを考えよう。

ここで、もし「全体でA組以上B組にせよ」という状態になった場合、「追加の国の人が0組以上(B-A-1)組以下いる状態で、合計B人にせよ」とみなすことができるので、国を1個追加することで、最小値を無視できるようになる。

あとは(N+1)個の国の最大組数が指定された状態で、全体をB組構築する組み合わせの数え上げとなる。
これは包除原理の要領で2^(N+1)通り、条件に違反する国が確定されているケースを数え上げよう。
ここでは任意modにおける重複組み合わせBinom(p,q)を求める必要があるが、qが高々(N+1)個なので、p～(p-N)を並べて、1～(N+1)それぞれで割った後にp～(p-N)の積を取れば、任意modにおける除算を避けることができる。

ll mo;

ll comb(ll N, ll C) {
	if(N-C<C) C=N-C;
	
	vector<int> V;
	int i;
	FOR(i,C) V.push_back(N-i);
	for(i=C;i>=1;i--) {
		int b=i;
		FORR(v,V) {
			int a=__gcd(v,b);
			v/=a;
			b/=a;
		}
	}
	ll ret=1;
	FORR(v,V) ret=ret*v%mo;
	
	return ret;
	
}
ll hcomb(ll P_,ll Q_) { return (P_==0&&Q_==0)?1:comb(P_+Q_-1,Q_);}

class SpaceMission {
	public:
	int count(vector <int> minn, vector <int> maxn, vector <int> parity, int mint, int maxt, int modulus) {
		int N=minn.size();
		int i;
		mo=modulus;
		
		if(mo==1) return 0;
		
		
		FOR(i,N) if(parity[i]) {
			minn[i]--;
			maxn[i]--;
			minn[i]=max(0,minn[i]);
			mint--;
			maxt--;
			if(minn[i]>maxn[i]) return 0;
		}
		mint=max(mint,0);
		if(maxt<mint) return 0;
		mint=(mint+1)/2;
		maxt=maxt/2;
		FOR(i,N) {
			minn[i]=(minn[i]+1)/2;
			maxn[i]=maxn[i]/2;
			if(minn[i]>maxn[i]) return 0;
			mint-=minn[i];
			maxt-=minn[i];
			if(mint<0) mint=0;
			if(maxt<0) return 0;
			maxn[i]-=minn[i];
		}
		cout<<mint<<" "<<maxt<<endl;
		if(mint>maxt) return 0;
		maxn.push_back(maxt-mint);
		
		ll ret=0;
		N++;
		int mask;
		FOR(mask,1<<N) {
			ll sum=0;
			int mul=1;
			FOR(i,N) if(mask&(1<<i)) {
				mul=-mul;
				sum+=maxn[i]+1;
			}
			if(sum>maxt) continue;
			ll pat=hcomb(N,maxt-sum);
			(ret+=mul*pat)%=mo;
		}
		return (ret%mo+mo)%mo;
	}
}

まとめ

これChatでも言われてたけど、任意modの二項係数の求め方が主題？
偶奇関連の問題設定、何の面白さにかかわってるかわからないし、そこで自分はミスして落としたので残念。