AtCoder ABC #215 : H - Cabbage Master

良い練習問題。
https://atcoder.jp/contests/abc215/tasks/abc215_h

問題

N種類のキャベツがあり、各個数A[i]が与えられる。
また、M種類の企業があり、求めるキャベツの個数B[i]が与えられる。
加えて、各企業がどのキャベツを受け取るかが与えられる。

キャベツを受け取り可能な企業にそれぞれ配るばあい、どう配っても求めるキャベツ数を達成できないよう、キャベツを減らしたい。
減らすべき最小キャベツ数と、減らし方の組み合わせを求めよ。

解法

F(mask) := キャベツの種類のbitmaskがmaskであるようなものを受け入れる、企業の求めるキャベツの総和
G(mask) := キャベツの種類のbitmaskがmaskであるようなものの総個数
とする。
F(mask)は高速ゼータ変換で計算できる。
Hallの結婚定理を考えると、全maskについてG(mask)≧F(mask)なら条件を満たすキャベツの配り方があることになる。

逆に、F(mask)が正の場合、G(mask)-(F(mask)-1)だけキャベツを減らせば、条件を満たせないことになる。
そこで、減らすべき最小キャベツ数はG(mask)-(F(mask)-1)の最小値である。

次に組み合わせを考える。
上記減らすべき最小キャベツ数をKとおく。
H(mask) := 減らすキャベツK個を選ぶとき、最低1個以上減らしているような種類がちょうどmaskに相当するものの組み合わせ
T(mask) := 減らすキャベツK個を選ぶとき、最低1個以上減らしているような種類がちょうどmaskに相当する場合、条件を満たさない事態が発生する

と置くと、T(mask)が真であるH(mask)の総和が組み合わせ数である。
H(mask)はH(mask)=Binom(G(mask),K)から初めて高速メビウス変換で求めることができる。
T(mask)は、T(mask) = (G(mask)-(F(mask)-1))==Kから初めて高速ゼータ変換で求めることができる。

int N,M;
int A[20],B[10100];
int C[101010];
ll F[1<<20];
ll G[1<<20];
ll H[1<<20];
int tar[1<<20];
const ll mo=998244353;

ll comb(ll N_, ll C_) {
	const int NUM_=2400001;
	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(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>>A[i];
	FOR(i,M) cin>>B[i];
	FOR(y,N) FOR(x,M) {
		cin>>i;
		if(i) C[x] |= 1<<y;
	}
	FOR(x,M) F[C[x]]+=B[x];
	FOR(i,N) FOR(x,1<<N) if(x&(1<<i)) {
		F[x]+=F[x^(1<<i)];
		G[x]+=A[i];
	}
	ll mi=1LL<<60;
	FOR(i,1<<N) if(F[i]) mi=min(mi,G[i]-F[i]+1);
	
	
	if(mi<=0) {
		cout<<"0 1"<<endl;
		return;
	}
	FOR(i,1<<N) {
		if(F[i]&&G[i]-F[i]+1==mi) tar[i]=1;
		H[i]=comb(G[i],mi);
	}
	FOR(i,N) FOR(x,1<<N) {
		if(x&(1<<i)) (H[x]+=mo-H[x^(1<<i)])%=mo;
		else tar[x]|=tar[x^(1<<i)];
	}
	ll ret=0;
	FOR(i,1<<N) if(i&&tar[i]) ret+=H[i];
	cout<<mi<<" "<<(ret%mo)<<endl;
	
}

まとめ

それぞれをちゃんと理解していますか？を問う問題。