兩道容斥計(jì)數(shù)

CF451E. Devu and Flowers

題意

有 \(n(1\le n\le 20)\) 個(gè)不同顏色的球，每種顏色的球有 \(f_i(1\le f_i \le 10^{12})\) 個(gè)，問拿 \(s(1\le s\le 10^{14})\) 個(gè)球的方案數(shù)。

題解

考慮生成函數(shù)

求這玩意 \(x^s\) 的系數(shù)，因?yàn)榉肿拥膬缱疃嗑?\(2^n\) 中，把分子每個(gè)冪的貢獻(xiàn)算一下就完事。

AC代碼

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
using ll = long long;

constexpr int N = 55, P = 1e9+7;
ll fac[N];

ll qpow(ll a, ll b) {
	ll res=1;
	for(;b;b>>=1,a=a*a%P)if(b&1)res=res*a%P;
	return res;
}

ll C(ll n, ll k) {
	if (k > n) return 0;
	if (k > n-k) k = n-k;
	ll res = 1;
	rep(i,0,k)res=(n-i)%P*res%P;
	return res*qpow(fac[k], P-2)%P;
}

void pre() {
	fac[0] = 1;
	rep(i,1,50) fac[i] = fac[i-1]*i%P;
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin);
#endif
	cin.tie(nullptr)->ios::sync_with_stdio(false);
	pre();
	ll n,s,ans=0; cin>>n>>s;
	vector<ll> a(n);
	rep(i,0,n)cin>>a[i];
	rep(st,0,(1<<n)){
		ll pw=0, coe=0;
		rep(i,0,n){
			if((st>>i)&1){
				pw+=a[i]+1;
				coe ++;
			}
		}
		if(pw>s) continue;
		if(coe&1) ans=(ans-C(n+s-pw-1,n-1)+P)%P;
		else ans=(ans+C(n+s-pw-1,n-1))%P;
	}
	cout<<ans<<"\n";
	return 0;
}

注意第 20 行，必須先模后乘，否則爆long long。
本題也有容斥做法，也就是枚舉超出其范圍的那些。也就是0個(gè)違法-1個(gè)違發(fā)+2個(gè)違法。。。

下面以CCPC2021 威海M舉例。

CCPC2021 威海M 810975

題意

給定 \(n,m,k\) ,問有多少個(gè)長(zhǎng)度為 \(n\) 的 \(01\) 串，其中有 \(m\) 個(gè) \(1\) ，且 連續(xù)的 \(1\) 的個(gè)數(shù)不能超過 \(m\) ，且要確切的有一個(gè)長(zhǎng)度為 \(k\) 的連續(xù)的 \(1\) 。

題解

考慮容斥。其中，“確切”的有一個(gè)長(zhǎng)度為 \(k\) 的連續(xù)的 \(1\) ，可以容斥掉，也即：最大連續(xù)的 \(1\) 的長(zhǎng)度為 \([0,k]\) 的減去 \([0,k-1]\) 的就行。

把這個(gè)條件去掉之后，由于有 \(n-m\) 個(gè) \(0\) ，考慮隔板法，有 \(n-m+1\) 個(gè)空，于是得到如下方程：

枚舉大于 \(k\) 的 \(x_i\) 的個(gè)數(shù)，將這些 \(x_i\) 減去 \(k+1\) ，那等式右邊就成了 \(m-num\times (k+1)\) ，就化成沒有約束一般問題了。

時(shí)間復(fù)雜度 \(O(n)\)

AC代碼

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
using ll = long long;

constexpr int N = 1e5+5, P = 998244353;
ll fac[N], inv[N];
ll n,m,k;

ll qpow(ll a, ll b) {
	ll res=1;
	for(;b;b>>=1,a=a*a%P)if(b&1)res=res*a%P;
	return res;
}

ll C(ll a, ll b) {
	if (b > a) return 0;
	return fac[a]*inv[b]%P*inv[a-b]%P;
}

ll calc(ll d) {
	ll ans=0;
	d++;
	rep(i,0,n-m+2){
		if(i&1)ans=(ans-C(n-m+1,i)*C(n-i*d,n-m)%P+P)%P;
		else ans=(ans+C(n-m+1,i)*C(n-i*d,n-m)%P)%P;
	}
	return ans;
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin);
#endif // !ONLINE_JUDGE
   	cin.tie(nullptr)->ios::sync_with_stdio(false);
    cin>>n>>m>>k;
	if(m>n){
		cout<<0;
		return 0;
	}
	if(k>m){
		cout<<0;
		return 0;
	}
	fac[0] = inv[0] = 1;
	rep(i,1,N)fac[i]=fac[i-1]*i%P;
	inv[N-1] = qpow(fac[N-1],P-2);
	for(int i=N-2;i>=1;i--)inv[i]=inv[i+1]*(i+1)%P;
	cout<<(calc(k)-calc(k-1)+P)%P<<"\n";
    return 0;
}