Solution
延续上一题的思路，发现只与 \(1\) 和 \(-1\) 的数量有关，设 \(1\) 的数量为 \(a\)，\(-1\) 的数量为 \(b\)。上一题的构造方案为 \(1\) 和 \(-1\) 交替放，再把剩余的放在末尾。
当 \(a\le b\) 时，最后剩余的是 \(-1\)，显然最大子段和为 \(1\)。所以只要保证没有相邻的 \(1\) 即可，看作在 \(-1\) 里面插 \(1\)，方案数根据插板法可得：
\[\binom{b+1}{a} \]当 \(a>b\) 时，最后剩余的 \(1\) 的数量就是最大子段和，即 \(a-b\)。
考虑如何求出方案数，有一个非常重要的性质：任何一个前缀的值在区间 \([0,a-b]\)。
证明可以采用反证法，假设存在一个以 \(i\) 结尾的前缀满足小于 \(0\) 或大于 \(a-b\)，那么：
-
如果小于 \(0\)，因为整个序列的和为 \(a-b\)，那么以 \(i+1\) 为开始的后缀就会大于 \(a-b\)，不满足最大子段和为 \(a-b\)。
-
如果大于 \(a-b\)，显然这就不满足条件。
故假设不成立，原命题成立。
所以设计 DP 方程 \(f(i,j)\) 表示填到第 \(i\) 个数和为 \(j\) 的方案数，根据上文的性质有 \(0\le j \le a-b\)，不然没法 DP。有转移方程：
\[f(i,j)=f(i-1,j+1)+f(i-1,j-1) \]注意特判 \(j=0\) 即可，答案为 \(f(n,a-b)\)，要把第一维滚掉。
Code
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using ull=unsigned long long;
inline void read(int &x){
char ch=getchar();
int r=0,w=1;
while(!isdigit(ch))w=ch=='-'?-1:1,ch=getchar();
while(isdigit(ch))r=(r<<1)+(r<<3)+(ch^48),ch=getchar();
x=r*w;
}
const int N=1e4+7,mod=998244353;
int f[2][N];
int Pow(int x,int y){
int ans=1;
while(y){
if(y&1)ans=ans*x%mod;
x=x*x%mod;
y>>=1;
}
return ans;
}
int C(int n,int m){
if(n<m)return 0;
if(m==0)return 1;
int ans=1;
for(int i=1;i<=m;i++)
ans=ans*(n-i+1)%mod,ans=ans*Pow(i,mod-2)%mod;
return ans;
}
main(){
int n;read(n);
int a=0,b=0;
for(int i=1,x;i<=n;i++){
read(x);
if(x==1)a++;
else b++;
}
if(a<=b)printf("%lld\n",C(b+1,a));
else{
f[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=a-b;j++){
int op=i&1;
if(j==0)f[op][j]=f[op^1][j+1]%mod;
else f[op][j]=(f[op^1][j-1]+f[op^1][j+1])%mod;
}
printf("%lld\n",f[n&1][a-b]);
}
return 0;
}