Codeforces ECR #094 : G. Mercenaries

珍しくECRの最終問の割に難易度低め。
https://codeforces.com/contest/1400/problem/G

問題

N人の技師がいる。
ここから何人かを選びたい。
i番目の技師は、最終的にL[i]人以上R[i]以下が選ばれている状態でなければ選ぶことができない。

加えて、M個の条件がある。
これは2人同時に選べないような2人組からなる。

各条件を満たす技師の選び方は何通りか。

解法

事前に以下を求めておく。

• f(n) := n人選ぶ状態が許可されるような技師の人数m
• g(x,y) := すでにy人選ぶ人が確定しているとき、全体でx人選ぶ前者の条件を満たす選びから

g(x,y) = Binom(f(x)-y,x-y)+g(x-1,y) なので、二項係数で事前に列挙しておけばf(n)がO(N)、g(x,y)がO(NM)で求められる。

あとは、Mが小さいので、包除原理で解こう。
すなわち、M個の条件のうち違反することが確定する条件を列挙したとき、その条件を満たす組み合わせを計算できればよい。
これは上述のg(x,y)を使えばO(1)で求めることができる。

int N,M;
int L[303030],R[303030];
int A[21],B[21];
int S[303030];
int T[303030];
int sel[303030];
ll num[303030][41];
const ll mo=998244353;
ll comb(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	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(N_<0 || C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>L[i]>>R[i];
		T[L[i]]++;
		T[R[i]+1]--;
	}
	FOR(i,M) {
		cin>>A[i]>>B[i];
		A[i]--;
		B[i]--;
	}
	
	for(i=1;i<=N;i++) {
		T[i]+=T[i-1];
		FOR(j,41) num[i][j]=(comb(T[i]-j,i-j)+num[i-1][j])%mo;
	}
	
	ll ret=0;
	int mask;
	FOR(mask,1<<M) {
		int TL=1,TR=N,del=0;
		FOR(i,M) if(mask&(1<<i)) {
			if(sel[A[i]]==0) {
				del++;
				sel[A[i]]++;
				TL=max(TL,L[A[i]]);
				TR=min(TR,R[A[i]]);
			}
			if(sel[B[i]]==0) {
				del++;
				sel[B[i]]++;
				TL=max(TL,L[B[i]]);
				TR=min(TR,R[B[i]]);
			}
		}
		
		TL=max(TL,del);
		if(TL<=TR) {
			ll tmp=num[TR][del]-num[TL-1][del];
			if(__builtin_popcount(mask)%2==1) {
				ret-=tmp;
			}
			else {
				ret+=tmp;
			}
		}
		
		FOR(i,M) sel[A[i]]=sel[B[i]]=0;
	}
	
	cout<<(ret%mo+mo)%mo<<endl;
	
	
}

まとめ

最終問が易しめなの珍しい。