不难发现 $0$ 和 $1$ 执行and
和or
操作时,相当于把其中一个元素删掉了。而 $00$ 之间或者 $11$ 之间执行and
和or
操作时,也可以认为是删掉了其中一个。
那么问题转化为每次删除一个数,最后剩下的元素是 $1$ 的方案数,我们可以枚举最后剩下的那个 $1$ ,然后求出删左边和删右边的方案数。
以删左边为例,定义 $f_i$ 表示删除 $i$ 个元素的方案数,转移方案有两种:
这是因为删除第一个元素的时候只能选择和右边进行删除,其余位置既可以和左边也可以和右边进行删除(最右边的元素的右边也有元素,即选择留下来的那个)。
因此 $f_i=(2i-1)f_{i-1}$ ,并且不难发现右边和左边求法一致。
最后的答案就是 $\sum_{A_i=1}f_{i-1}f_{n-i}{n-1\choose i-1}$ ,其中 $n-1\choose i-1$ 表示两边删除顺序穿插的方案数。
#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=1000000,MOD=998244353;
int n,a[maxn+5],fac[maxn+5],INV[maxn+5],f[maxn+5],ans;
#define ADD(x,y) (((x)+(y))%MOD)
#define MUL(x,y) ((LL)(x)*(y)%MOD)
void Make(int n){
INV[0]=INV[1]=1;for (int i=2;i<=n;i++) INV[i]=MUL(MOD-MOD/i,INV[MOD%i]);
fac[0]=1;for (int i=1;i<=n;i++) fac[i]=MUL(fac[i-1],i),INV[i]=MUL(INV[i],INV[i-1]);
}
inline int C(int x,int y) {return x<y?0:MUL(fac[x],MUL(INV[y],INV[x-y]));}
int main(){
scanf("%d",&n);Make(n);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
f[0]=1;for (int i=1;i<=n;i++) f[i]=MUL(f[i-1],(i<<1)-1);
for (int i=1;i<=n;i++) if (a[i]) ans=ADD(ans,MUL(MUL(f[i-1],f[n-i]),C(n-1,i-1)));
printf("%d\n",ans);return 0;
}