您的位置: 首页  >  IT文章  >  【arc102E】Stop. Otherwise...

【arc102E】Stop. Otherwise...

分类: IT文章 • 2022-06-04 17:14:16

Portal --> arc102E

Description

　　有(N)个位置，每个位置可以填一个(1sim K)的数，要求对于每一个(iin [2,2K])，求出任意两个位置的和都不为(i)的填法数量对(998244353)取模的结果，位置与位置之间没有区别

　　

Solution

　　一开始想的是容斥。。结果。。实际上并不需要容斥也能直接做

　　是道疯狂插板的。。奇妙题目

​　　我们可以先考虑一下如果没有任何限制，就只是往(N)个位置里面填数，那么其实相当于把(N)个位置分配给(1sim K)这(K)个数，每个数对应的位置数量(>=0)，那么直接插板就是(inom {N+K-1} {K-1})，具体为什么的话就是插板本身解决的最裸的问题是把(n)个物品分成(k)份的方案数为(inom {n-1}{k-1})，也就是(n-1)个缝隙里面选(k-1)个插个板，这样就分成了(k)份了，但是这个计算方式要求每一份的数量(>=1)，而在这题没有任何限制的情况下，我们每份是要(>=0)的，那就直接每份先多加一个，也就是总共加(K)个，在最后的分配方案中每组拿走一个就可以得到一个合法的方案了

​　　但是现在的问题是有限制，我们将限制用简洁直观一点的语言列出来：

1、一种方案中(x)和(i-x)不能同时存在

2、如果(i)是偶数，那么一种方案中(frac{i}{2})要么出现(1)次要么不出现

​　　

​　　发现第二个限制其实。。情况很少，所以我们可以把它单独拿出来搞一下，我们在计算前先钦定(frac{i}{2})的出现次数是(0)还是(1)（当然如果说(i)不是偶数那就不用管了直接算），然后后面就不用管这个数了，那么剩下的问题就变成了这样：有若干对形如((x,i-x))的限制，一对限制中两个数不能同时出现，并且有另外一些数可以随便填，我们要用这些数来填若干个位置

​　　这个的话同样也是可以直接用组合数进行计算的，具体一点的话就是：假设限制的数量是(x)对（注意这里的(x)与上面提到的(x)意义不同），另外有(y)个数不受限，我们要填(z)个位置

​　　考虑钦定(z)个位置中，哪些位置填的是受限的数字，不妨设这样的位置的数量为(q)，那么总共有(inom x qcdot 2^q)种不同的选择方式（从(x)对限制中选出(q)对，每对可以选择填入第一个数字或者第二个数字），确定了这些受限的数字之后，可填的数字集合就确定了，现在我们总共有(q+y)种数字可以填，其中(q)种数字必须出现至少一次，其他(y)种数字可以不出现，我们现在要将(z)个位置分配给不同的数字，那么就又变回前面的插板法了，方案数为(inom {z+y-1}{q+y-1})

​　　所以，对于一对((x,y,z))，我们可以枚举(q)算出其对应的方案数（记为(f(x,y,z))好了）：

[f(x,y,z)=sumlimits_{q=0}^zinom x qcdot 2^qcdot inom{z+y-1}{q+y-1} ]

​　　那么答案就很好求了：

[Ans_i=egin{cases} f(cnt/2,K-cnt,N)&(i\%2=1)\ \ f((cnt-1)/2,K-cnt,N)+f((cnt-1)/2,K-cnt,N-1)&(i\%2=0) end{cases} ]

​　　其中(cnt)表示满足(i-xin[1,K])且(xin[1,K])的(x)的数量

　　

​　　mark：（没有什么建设性的东西）多个条件的情况下，可以先按照情况少的那个条件分大类然后再在里面继续讨论其他情况

　　

​　　代码大概长这个样子

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=2010,MOD=998244353;
int C[N*2][N*2],pw[N*2];
int n,K,ans;
int plu(int x,int y){return (1LL*x+y)%MOD;}
int mul(int x,int y){return 1LL*x*y%MOD;}
void prework(int n){
	C[0][0]=1;
	for (int i=1;i<=n;++i){
		C[i][0]=1; C[i][i]=1;
		for (int j=1;j<i;++j)
			C[i][j]=plu(C[i-1][j-1],C[i-1][j]);
	}
	pw[0]=1;
	for (int i=1;i<=n;++i) pw[i]=mul(pw[i-1],2);
}
int f(int x,int y,int z){
	if (y<0) return 0;
	int ret=0;
	for(int q=0;q<=z&&q<=x;++q)
		if (q+y-1<=z+y-1&&q+y-1>=0) 
			ret=plu(ret,mul(C[x][q],mul(pw[q],C[z+y-1][q+y-1])));
	return ret;
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
#endif
	int cnt;
	scanf("%d%d",&K,&n);
	prework(n+K);
	for (int i=2;i<=2*K;++i){
		cnt=0;
		for (int j=1;j<=K;++j)
			if (1<=i-j&&i-j<=K) ++cnt;
		if (i&1)
			ans=f(cnt/2,K-cnt,n);
		else{
			ans=f((cnt-1)/2,K-cnt,n);
			ans=plu(ans,f((cnt-1)/2,K-cnt,n-1));
		}
		printf("%d
",ans);
	}
}

相关推荐