自动搬运

查看原文

来自洛谷，原作者为

	dead_X Still we rise

搬运于2025-08-24 22:30:28，当前版本为作者最后更新于2021-04-07 09:33:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

下文记 $R_i=2r_i-1$。

• $\text{type}=0$

显然如果答案存在，我们放完所有兵营后必定还剩下 $m-\sum R_i$ 个空位置。

因此，我们只需要在 $m-\sum R_i+n$ 个位置中，有序地选出 $n$ 个，依次将这些位置钦定为第 $i$ 个兵营，剩余位置定为空地，即可算出所有方法数。

• $\text{type}=1$

考虑钦定两侧兵营的 $r_i$。

若最左侧为第 $p$ 个兵营，最右侧为第 $q$ 个兵营，将 $m$ 向左延长 $R_p-r_p$ 格子，向右延长 $R_q-r_q$ 个格子，同时让所有兵营的摆放条件仍然按照 $\text{type}=0$ 时的条件计数，方法仍然可以形成一一对应，只需要将延长出来的格子去掉即可。

因此，我们可以做到 $O(n^2+m)$，但是过不去。

注意到 $r_i$ 的值域只有 $10^3$，我们可以转而枚举 $r_i$，这样的复杂度为 $O(r_i^2+m)$，即可通过。

代码

//愿神 zhoukangyang 指引我。
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
int a[1000003],b[1000003];
const int p=998244353;
int n=read(),m=read(),op=read();
int qp(int x,int y)
{
	int res=1;
	for(int t=x; y; y>>=1,t=t*t%p) if(y&1) res=res*t%p;
	return res;
}
int fac[1000003],ifac[1000003];
int A(int n,int m)
{
	if(n<m) return 0;
	return fac[n]*ifac[n-m]%p;
}
int C(int n,int m)
{
	if(n<m) return 0;
	return fac[n]*ifac[n-m]%p*ifac[m]%p;
}
void solve0()
{
	int s=0;
	for(int i=1; i<=n; ++i) s+=a[i];
	if(s>m)
	{
		puts("0");
		return ;
	}
	int A=(m-s)+n,ans=1;
	for(int i=A; i>A-n; --i) ans=ans*i%p;
	printf("%lld\n",ans);
	return ;
}
int G[2003],S[1003];
void solve1()
{
	if(n==1)
	{
		printf("%lld\n",m);
		return ;
	}
	int s=0;
	fac[0]=ifac[0]=1;
	for(int i=1; i<=m; ++i) fac[i]=fac[i-1]*i%p,ifac[i]=qp(fac[i],p-2);
	for(int i=1; i<=n; ++i) s+=a[i];
	int ans=0;
	for(int i=1; i<=n; ++i) 
	{
		for(int j=0; j<=1000; ++j) G[b[i]+j]=(G[b[i]+j]+S[j])%p;
		++S[b[i]];
	}
	for(int i=0; i<=2000; ++i) if(G[i]) ans=(ans+G[i]*A(m+i-s+n,n)%p)%p;
	printf("%lld\n",ans*qp(C(n,n-2),p-2)%p);
	return ;
}
signed main()
{
	for(int i=1; i<=n; i++) b[i]=read(),a[i]=(b[i]<<1)-1,--b[i];
    if(op) solve1();
    else solve0();
    return 0;
}