自动搬运

查看原文

来自洛谷，原作者为

	dAniel_lele 当你在幻想上天会给你开一扇窗的时候，你已经输一半了。

搬运于2025-08-24 22:43:13，当前版本为作者最后更新于2022-11-03 12:30:25，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

测试点 1~3

输出不可以，总司令 $0$ 即可。

测试点 4~5

输出 $[b_1=b_2]$。其实输出 $1$ 即可，我没给 $0$ 的点。

测试点 6~8

暴力，咋暴力都行，数据太小了。

测试点 9~11

这个可以用状压 $dp$，毕竟 $b_i=1$。

测试点 12~14

稍微转化一下，转化为：

有 $n$ 个人要完成 $\frac{n}{2}$ 份大作业，两个人一组完成大作业，需要按顺序提交作业，求方案数。

考虑对于每个人选搭档，第 $1$ 个人有 $n-1$ 种选择，第 $2$ 个人 $n-3$ 种，以此类推，最后乘 $\frac{n}{2}!$ 即可。

测试点 15~18

状压 dp，考虑每次操作已经选个 $0/1/2$ 个数组中的位置的方案数，可以压位存下来，转移只需要枚举数组这个位置要在哪些操作中被操作即可。复杂度还是要看实现，最快可以达到 $O(3^{\frac{\sum b_i}{2}}\times n)$，慢一点的也能过。

测试点 19~25

发现不同操作位置本质相同，首先考虑 $dp_{i,j,k}$ 表示看到第 $i$ 个数组位置，有 $j$ 个操作位置目前为 $1$，$k$ 个为 $2$。转移需要枚举往目前 $0/1$ 个的位置分别转移多少个，复杂度 $O((\sum b_i)^2(n+\sum b_i))$，可以通过 $19\sim 20$ 点。

容易发现只需要记录 $2$ 操作个数，$0/1$ 操作个数都可以通过某些方式计算，时间与空间复杂度变为 $O((\sum b_i)(n+\sum b_i))$，可以通过 $21\sim 22$ 点。

然后分析一下，实际上操作位置只有 $\frac{\sum b_i}{2}$ 个，同时空间可以滚动数组优化，最终复杂度为 $O((\sum b_i)^2)$，$\frac{1}{4}$ 倍常数，实际循环次数约为 $2.25\times 10^8$，可以通过本题。

代码

#include <bits/stdc++.h>
using namespace std;
const int mod=998244353;
int qp(int a,int b){
	int ans=1;
	while(b){
		if(b&1) ans=((long long)ans*a)%mod;
		a=((long long)a*a)%mod;
		b>>=1;
	}
	return ans;
}
int fac[100005],inv[100005];
void init(){
	fac[0]=1;
	for(int i=1;i<=100000;i++) fac[i]=(long long)fac[i-1]*i%mod;
	inv[100000]=qp(fac[100000],mod-2);
	for(int i=99999;i>=0;i--) inv[i]=(long long)inv[i+1]*(i+1)%mod;
}
int C(int i,int j){
	if(i<0||j<0||i<j) return 0;
	return (long long)fac[i]*inv[i-j]%mod*inv[j]%mod;
}
int b[50005],n,pre[50005],dp[2][50005];
signed main(){
	init();
	cin>>n;
	for(int i=1;i<=n;i++) cin>>b[i],pre[i]=pre[i-1]+b[i];
	if(pre[n]%2==1) return cout<<0,0;
	int sum=pre[n]/2;
	dp[0][0]=1;
	for(int i=1;i<=n;i++){
	    for(int j=0;j<=sum;j++){
			int tp2=j,tp1=pre[i-2]-j*2,tp0=sum-tp2-tp1;
			if(tp0<0) continue;
			dp[i&1][j]=0;
	    }
		for(int j=0;j<=sum;j++){
			int tp2=j,tp1=pre[i-1]-j*2,tp0=sum-tp2-tp1;
			if(tp0<0) continue;
			for(int k=0;k<=b[i];k++){
				if(tp1<k||tp0<b[i]-k) continue;
				if(dp[(i&1)^1][tp2]) (dp[i&1][tp2+k]+=(long long)dp[(i&1)^1][tp2]*C(tp1,k)%mod*C(tp0,b[i]-k)%mod)%=mod;
			}
		}
	}
	cout<<dp[n&1][sum];
	return 0;
}