题目概述

CF GYM 102978B

解题报告

不难发现 $0$ 和 $1$ 执行and和or操作时，相当于把其中一个元素删掉了。而 $00$ 之间或者 $11$ 之间执行and和or操作时，也可以认为是删掉了其中一个。

那么问题转化为每次删除一个数，最后剩下的元素是 $1$ 的方案数，我们可以枚举最后剩下的那个 $1$ ，然后求出删左边和删右边的方案数。

以删左边为例，定义 $f_i$ 表示删除 $i$ 个元素的方案数，转移方案有两种：

• 先删第一个元素：$f_{i-1}$
• 先删后面的元素：$2(i-1)f_{i-1}$

这是因为删除第一个元素的时候只能选择和右边进行删除，其余位置既可以和左边也可以和右边进行删除（最右边的元素的右边也有元素，即选择留下来的那个）。

因此 $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;
}