ZigZagK的博客
[思维+DP]XXI Opencup GP of Tokyo B【Bit Operation】题解
2021年3月24日 17:00
查看标签

题目概述

CF GYM 102978B

解题报告

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

那么问题转化为每次删除一个数,最后剩下的元素是 $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;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!