526互联

Atcoder Regular Contest 156 E - Non-Adjacent Matching

发布时间 2023-07-14 11:32:43作者: tzc_wk

感觉可能没有银牌的难度（？），感觉有的铜牌题比这要难一些。

先猜一下什么样的 \(\{x_i\}\) 是合法的。结论是 \(\forall i,x_i+x_{i\bmod n+1}\le S-(x_i+x_{i\bmod n+1})\)，且 \(S\) 是偶数。必要性显然。充分性就考虑如果不存在任何一个 \(i\) 满足 \(x_i+x_{i\bmod n+1}\ge S-(x_i+x_{i\bmod n+1})-1\)，那么 xjb 匹配一个后也满足上面的条件。否则可以证明最多只有两个这样的 \(i\)，如果有一个那么选一个 \(i\) 选一个与 \(i\) 不相邻的点，如果有两个那么在两组中各挑一个点使得它们相邻，这样后面还是满足这个条件。

接下来考虑怎么计数。对存在几个 \(i\) 满足 \(2(x_i+x_{i\bmod n+1})>S\) 分类讨论：

  • \(0\) 个，那么考虑 \(F(x)=(\dfrac{x^{m+1}-1}{x-1})^n\)，我们要求的东西实际上是 \(\sum\limits_{i=0}^k[x^i]F(x)\)，我们枚举上面 \(x^{m+1}\) 项取了几个以后可以做到 \(O(n^2)\)。
  • \(1\) 个，那么设 \(dp_{i,j}\) 表示前 \(i\) 个数和是 \(j\) 的方案数，然后枚举这两个数之和做一遍前缀和即可。
  • \(2\) 个，那么可以证明这两个位置一定相邻，否则假设存在两个位置 \(i,j\) 满足 \(2(x_i+x_{i\bmod n+1})>S\) 且 \(i,i\bmod n+1,j,j\bmod n+1\) 四者互不相同，那么有 \(2S\ge 2(x_i+x_{i\bmod n+1}+x_j+x_{j\bmod n+1})>2S\)，不合要求。否则朴素做法是枚举这三个数，即 \(\sum\limits_{x}\sum\limits_{y}\sum\limits_{z}\sum\limits_{k}[x+y>z+s][y+z>x+s][x+y+z+s\le k][(x+y+z+s)\bmod 2=0]dp_{n-3,s}\)，然后你枚举 \(k,y\)，发现对 \(x,z\) 的限制是 \(|x-z|>y+s\) 且 \(x+z\le k-y-s\)，直接二维前缀和即可。

最后拿 \(0\) 个的方案数减去 \(1\) 个的方案数再加上 \(2\) 个的方案数即可，复杂度平方。

const int MAXNM=1e7;
const int MAXN=3000;
const int MOD=998244353;
int n,m,k,fac[MAXNM+5],ifac[MAXNM+5];
void init_fac(int n){
	for(int i=(fac[0]=ifac[0]=ifac[1]=1)+1;i<=n;i++)ifac[i]=1ll*ifac[MOD%i]*(MOD-MOD/i)%MOD;
	for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%MOD,ifac[i]=1ll*ifac[i-1]*ifac[i]%MOD;
}
int binom(int n,int k){if(n<0||k<0||n<k)return 0;return 1ll*fac[n]*ifac[k]%MOD*ifac[n-k]%MOD;}
int dp[MAXN+5][MAXN*4+5],sdp[MAXN+5][MAXN*4+5];
int sum[2][MAXN+5][MAXN*2+5],ss[2][MAXNM+5];
int main(){
	scanf("%d%d%d",&n,&m,&k);init_fac(MAXNM);int res=0;
	for(int i=0;i<2;i++){
		ss[i][0]=(!i)?1:0;
		for(int j=1;j<=k;j++)ss[i][j]=(ss[i][j-1]+((j%2==i)?binom(j+n-1,n-1):0))%MOD;
	}
	for(int i=0;i<=n;i++)if(k-i*(m+1)>=0){
		int prd=1ll*ss[i*(m+1)%2][k-i*(m+1)]*binom(n,i)%MOD;
		if(i&1)res=(res-prd+MOD)%MOD;else res=(res+prd)%MOD;
	}
	dp[0][0]=1;for(int i=0;i<=4*m;i++)sdp[0][i]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=4*m;j++){
			dp[i][j]=sdp[i-1][j];
			if(j-m-1>=0)dp[i][j]=(dp[i][j]-sdp[i-1][j-m-1]+MOD)%MOD;
		}
		sdp[i][0]=dp[i][0];
		for(int j=1;j<=4*m;j++)sdp[i][j]=(sdp[i][j-1]+dp[i][j])%MOD;
	}
	for(int s=0;s<=m*2;s++)for(int l=0;l<s;l++)if((l+s)%2==0&&l+s<=k)
		res=(res-1ll*dp[n-2][l]*n%MOD*min(s+1,m*2+1-s)%MOD+MOD)%MOD;
	for(int i=0;i<=m;i++)for(int l=0;l<=m;l++)sum[(i+l)%2][abs(l-i)][l+i]++;
	for(int i=0;i<2;i++)for(int j=0;j<=m;j++)for(int l=0;l<=m*2;l++){
		if(j)sum[i][j][l]+=sum[i][j-1][l];
		if(l)sum[i][j][l]+=sum[i][j][l-1];
		if(j&&l)sum[i][j][l]-=sum[i][j-1][l-1];
	}
	for(int t=0;t<=m;t++)for(int j=0;j<=m;j++)if(j-t-1>=0&&k-t-j>=0)
		res=(res+1ll*dp[n-3][t]*n%MOD*sum[(t+j)%2][j-t-1][min(k-t-j,m*2)])%MOD;
	printf("%d\n",res);
	return 0;
}