XXI Opencup GP of Tokyo B【Bit Operation】

题目大意

戳我读原题

给出一串 $01$ 数列，每次操作选择数 $i$ 和 $i+1$ 进行 $or$ 和 $and$

运算，然后删除这两个数，加入一个运算结果，直到剩下一个数为止，求$(2^{n-1})*(n-1)!$的删除方案中最后剩下$1$的数量。

解题思路

对于任意两数组合$00\quad01\quad10\quad11$进行的操作都可以看作是删除一个数，留下另一个数，那么问题转化为每次删除一个数，最后剩下$1$的方案有多少。

所以我们只需对每一个$1$统计删除方案数量即可。

对于一个左边删除$x$个，右边删除$y$个的状态$(x,y)$，因为左右两边各自的删除不会互相影响，所以先考虑一边。从$x-1$转移到$x$，有两种不同的删除方案

$1. 删除第一个元素：1种$

$2.删除其他元素：2种$

因为第一个元素只能与右边的元素进行删除，其余元素既可以和左边也可以和右边进行删除，所以从$x-1$转移到$x$，总共有$2*x-1$种方案。

而对于$y$来说也是同样有$2*y-1$种方案，所以对于状态$(x,y)$从$(0,0)$转移的方案数为$(2x-1)!(2y-1)!\binom{x+y}{x}$

其中$\binom{x+y}{x}$表示左右删除顺序的方案数。对于$A_i==1$，$x=i-1,y=n-i$

预处理后对每一个$A_i==1$就可以$O(1)$实现计算方案数。

解题代码

#include <cstdio>
using namespace std;
#define LL long long
const int N=1000005,P=998244353;
int n,a[N],ans;
int f[N],inv[N],fac[N];
inline int Add(int x,int y){return (x+y)%P;}
inline int Mul(int x,int y){return (((LL)x*y)%P);}
void Pre(int n)
{
    inv[0]=inv[1]=1;for (int i=2;i<=n;i++) inv[i]=Mul(P-P/i,inv[P%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()
{
    register int i,j;
    scanf("%d",&n);Pre(n);for (i=1;i<=n;i++) scanf("%d",&a[i]);
    f[0]=1;for (i=1;i<=n;i++) f[i]=Mul(f[i-1],(2*i)-1);
    for (i=1;i<=n;i++)
    if (a[i])
    {
        ans=Add(ans,(Mul(Mul(C(n-1,i-1),f[i-1]),f[n-i]) ) );
    }
    printf("%d",ans);
}