题解：AT_agc036_c [AGC036C] GP 2

本题相当于要对这样的序列进行计数：

$\sum_{i=1}^{n}a_i=3\times m$
$\max\left\{ a_i\right \}\le 2\times m$
$\sum_{i=1}^{n} a_i\pmod2\le m$

看到这种题可以往容斥的角度上面去思考。本题考虑对第二个限制进行容斥。

首先考虑去掉第二个限制。枚举奇数位置的个数

i

，数量为

C_n^i

。接下来相当于这些位置被填上了

1

，

n

个位置都再填一个偶数。相当于有

\frac{3\times m-i}{2}

个球要用

n-1

个板隔开。

接下来考虑不满足第二个限制的情况，发现此时必然满足第三个限制。原因留给读者思考。相当于在某一个盒子内放置了

2\times m+1

个球，剩下的隔板。仍然要枚举是拿一个盒子放多了，不过可以简简单单乘以

n

搞定。

设

n,m

同阶，通过线性求逆元可以做到

O(n+\log V)

。

CPP

#include<bits/stdc++.h>
#define int long long
#define mp(a,b) make_pair(a,b)
using namespace std;

inline int read(){
	int a=0,b=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')	b=-1;
		c=getchar();
	}
	while(isdigit(c)){
		a=(a<<1)+(a<<3)+(c-'0');
		c=getchar();
	}
	return a*b;
} 
inline void write(int x){
	if(x<0)	putchar('-'),x=-x;
	if(x>=10)	write(x/10);
	putchar(x%10+48);
}
inline void write1(int x){
	write(x),putchar(' '); 
} 
inline void write2(int x){
	write(x),putchar('\n');
}
const int N=5e6+15;
const int mod=998244353;
int jc[N];
int inv[N];
inline int qpow(int x,int y){
	if(y==0)	return 1;
	if(y==1)	return x;
	int ret=qpow(x,y/2);
	ret=ret*ret%mod;
	if(y&1)	ret=ret*x%mod;
	return ret;
}
void init(){
	jc[0]=1;
	for(int i=1;i<=5000000;i++){
		jc[i]=jc[i-1]*i%mod; 
	}
	inv[5000000]=qpow(jc[5000000],mod-2);
	for(int i=5000000;i>=1;i--){
		inv[i-1]=inv[i]*i%mod;
	}
	inv[0]=1;
//	cout<<inv[2]<<' '<<inv[3]<<endl;
}
int C(int x,int y){
	if(y<0)	return 0;
	if(y>x)	return 0;
	return jc[x]*inv[y]%mod*inv[x-y]%mod;
}
int n,m;
int include13,include13_fAKe;	//include13 代表第一次计算的答案 include13_fAKe 代表后面应当减去的答案  
#undef int
int main(){
	#define int long long
	init(); 
//	cout<<C(5,3)<<endl; 
	n=read(),m=read();
	//长度确定 和确定 最大值容斥 奇数个数较小 
	//和 为 3m 最大值 <=2m 奇数 <=m
	for(int i=0;i<=min(n,m);i++){
		if((3*m-i)%2!=0)	continue;
		//钦定数量的位置为奇数 然后是插板法 
		include13+=C(n,i)*C((3*m-i)/2+n-1,n-1)%mod;
		include13%=mod;
//		cout<<(3*m-i)/2+n<<' '<<n<<endl;
//		cout<<'&'<<include13<<endl;
	} 
	//第二部分 直接钦定一个位置为 2m+1 也就锁定了奇数最多 m 个 
	include13_fAKe=n*C(m+n-2,n-1)%mod;
	write2((include13-include13_fAKe+mod)%mod);
	return 0; 
}//一定要挽回罗琪钧的遗憾啊，一定会挽回罗琪钧的遗憾的！

题解：AT_agc036_c [AGC036C] GP 2

文章操作

相关推荐

评论

题解：AT_agc036_c [AGC036C] GP 2