The 2021 CCPC Weihai Onsite M - 810975（容斥）

写这题前，先把这道hdu6397经典题写了 。
题意：给定n,m,k，要求个m个格子填数，使每个数在[0,n-1]范围内，且他们的和为k。
思路：首先，不管[0,n-1]这个限制条件，考虑怎么用组合数算出方案。我是这样理解的，我们对选出的数取个前缀和，那么这m个数的前缀和必然在[0,k]这个区间内，且满足不递减，和最后一个数必然是k，由于最后一个数已经定了，那么问题变成选m-1个数，使他们不递减，且在[0,k]区间内，可以考虑插板法，对[1,k]的左边右边插板，插的每个板表示这个板要选择当前空隙的左边那个数，所以组合数就是C(k+m-1,m-1)；现在考虑[0,n-1]这个限制，显然可以容斥，所以问题转成怎么算至少有i个数超过n-1,且和为k的方案数，这又是一个经典组合数问题，我们可以把这个i个超过n-1的数都减去n，这样所有数都在[0,n-1]范围内，且和为k-ni，也可以理解为把和变为k-ni，然后把里面的i个数都加上n就符合条件了，所以方案是\(C(m,i) \times C(k+m-1-n*i,m-1)\);

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#include 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1000000 + 100;
const int INF = 0x7fffffff;
const int mod = 998244353;
const ll mod1 = 998244353;
const ll base = 137;
const double Pi = acos(-1.0);
const int G = 3;
int q_pow(int a, int b)
{
	int res = 1;
	while (b)
	{
		if (b & 1)
		{
			res = 1ll * res * a % mod;
		}
		b >>= 1;
		a = 1ll * a * a % mod;
	}
	return res;
}
int F[maxn], Finv[maxn], inv[maxn];
void init()
{
	inv[1] = 1;
	for (int i = 2; i < maxn; i++)
	{
		inv[i] = (mod - mod / i) * 1ll * inv[mod % i] % mod;
	}
	F[0] = Finv[0] = 1;
	for (int i = 1; i < maxn; i++)
	{
		F[i] = F[i - 1] * 1ll * i % mod;
		Finv[i] = Finv[i - 1] * 1ll * inv[i] % mod;
	}
}
int comb(int n, int m)
{
	if (m < 0 || m > n)
		return 0;
	return F[n] * 1ll * Finv[n - m] % mod * Finv[m] % mod;
}
int n,m,k;
int main()
{
	init();
	int t;
	cin >> t;
	while (t--)
	{
		scanf("%d%d%d", &n, &m, &k);
		int f=1;
		int ans=0;
		for(int i=0;i<=m;i++)
		{
			int uu=1;
			if(!f) uu=mod-1;
			f^=1;
			if(1ll*i*n>k+m-1) break;
			ans=(1ll*ans+1ll*uu*comb(m,i)%mod*comb(k+m-1-i*n,m-1)%mod)%mod;
		}
		printf("%d\n",ans);
	}
//	system("pause");
}

然后回到M. 810975这道题。
题意：给定n,m,k，构造长度为n的01串，使1的总数为m，且每个连续的1段长度最大值是k。
思路：首先对于最大值为k的这个条件，可以用最多有k个减去最多有k-1个容斥掉。然后考虑怎么算最多有k的方案。我们可以把两个连续的0中间看做一个长度为0的连续1段，那么问题转换成，构造n-m+1个连续1段，长度在[0,k]，且和为m。这跟上面那题就一模一样了，然后这题就解决了。
吐槽下，这周末的两场区域赛居然都考了容斥，还都是典中典，队友也没写过容斥，我还是得多学点容斥的套路...

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#include 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1000000 + 100;
const int INF = 0x7fffffff;
const int mod = 998244353;
const ll mod1 = 998244353;
const ll base = 137;
const double Pi = acos(-1.0);
const int G = 3;
int q_pow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
		{
			res=1ll*res*a%mod;
		}
		b>>=1;
		a=1ll*a*a%mod;
	}
	return res;
}
int F[maxn], Finv[maxn], inv[maxn];
void init(){
    inv[1] = 1;
    for(int i = 2; i < maxn; i ++){
        inv[i] = (mod - mod / i) * 1ll * inv[mod% i] % mod;
    }
    F[0] = Finv[0] = 1;
    for(int i = 1; i < maxn; i ++){
        F[i] = F[i-1] * 1ll * i % mod;
        Finv[i] = Finv[i-1] * 1ll * inv[i] % mod;
    }
}
int comb(int n, int m){
    if(m < 0 || m > n) return 0;
    return F[n] * 1ll * Finv[n - m] % mod * Finv[m] % mod;
}
int cal(int num,int lim,int sum)
{
	int f=1;
	int res=0;
	//cout<sum+num-1) break;
		res=(1ll*res+1ll*uu*comb(num,i)%mod*comb(num+sum-1-i*lim,num-1)%mod)%mod;
		f^=1;
	//	cout<
ACM容斥

相关

acm讲解

「acmhdu - 6314」Matrix

第十三届河南省ACM-ICPC游记

ACM模板

容斥原理及证明

Hyperf 接入阿里云ACM应用配置管理中心

[ACM] BFS & 双端BFS & A* & 双边BFS

计算几何 / Geometry（ACM-Template 2.0）

【luogu P3172】选数（数学）（容斥）（DP）

ACM入门方式

Linux 下使用 acme.sh 配置 Let's Encrypt 免费 SSL 证书 + 通配符证书

容斥原理

标签