「ZJOI2019」开关

神题

前言

设$\text{FWT}_{\oplus}(F(x))=F’(x)$

关于$\text{FWT}_{\oplus}$的展开式子，我发现大部分人都不晓得。。。。

$[x^S]F’(x)=\sum_T(-1)^{|S\cap T|} [x^T]F(x)$

$F(x)=\frac{F’’(x)} {2^n}$

详细可以看这个

定义$\bigoplus$为两个多项式的异或卷积

$\times$为两个多项式对应项直接相乘

$[x^S]F(x)$表示$F(x)$的第$S$项的系数

正文

翻转过程是一个$\oplus$的过程，所以考虑用集合幂指数配合$\text{FWT}_\oplus$构造和求解方程

事实上问题等价于从初始状态$S$跑到$\empty$的期望次数

设从$S$到$\empty$的期望次数生成函数为$F(x)$，其中$[x^{\empty}]F(x)=0$

设转移函数$G(x),[x^{ \{i\} }]G(x)=p_i$

那么我们的方程就是$F(x)\bigoplus G(x)+\sum x^S+cx^{\empty}=F(x)$

其中$x^S$表示这次转移之后答案要加一

由于直接这样转移得到的方程显然是无穷解的，因为无法保证$[x^{\empty}]F(x)=0$

所以我们用一个常数项$cx^{\empty}$平衡这个问题，$c$现在是未知的

$\because F(x)\bigoplus G(x)+\sum x^S+cx^{\empty}=F(x)$

$\therefore (F(x)\bigoplus G(x)+\sum x^S+cx^{\empty})’=F’(x)$

$\therefore F’(x)\times G’(x)+(\sum x^S+cx^{\empty})’=F’(x)$

我们模拟一下$G’(x)$

$[x^S]G’(x)=\sum_i(-1)^{|S\cap \{i\}|}[x^{ \{i\} }]G(x)=\sum_{i\notin S}p_i-\sum_{i\in S}p_i$

再卷一下$(\sum x^S+cx^{\empty})’$

$(\sum x^S)’=\sum_S\sum_T(-1)^{|S\cap T|}x^S$

$\because (-1)^{|S\cap T|} =\sum_{T\subset S}(-1)^|T|\cdot 2^{n-|S|}=[S=\empty]2^{n-|S|}$

$\therefore (\sum x^S)’=2^n x^{\empty}$

$(cx^{\empty})’=\sum c\cdot x^S$

然后我们带入反解$[x^S]F’(x)$

当$S=\empty$时,

则$[x^S]F’(x)\cdot [x^S]G’(x)+2^n+c=[x^S]F’(x)$

然后发现此时$[x^S]G’(x)=1$，那么就意味着$2^n+c=0$

解出了$c=-2^n$，但是此时我们实际上并不知道$[x^{\empty}]F’(x)$的值

当$S\ne \empty$时

$[x^S]F’(x)\cdot [x^S]G’(x)+c=[x^S]F’(x）$

$[x^S]F’(x)(1-[x^S]G’(x))=c$

我们考虑要求出$[x^\empty]F’(x)$的值

由$[x^{\empty}]F(x)=2^{-n}\cdot \sum [x^S] F’(x)=0$

那么我们由$F’(x)$回代得到$[x^S]F(x)(S \ne \empty)$

下面是一个背包，跑的同时统计一下就好了$|S\cap T|$的奇偶性就好了

然后会发现事实上并没有必要特判$S=\empty$的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cctype>
#include<vector>
using namespace std;

#define reg register
typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

#define pb push_back
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
int rd(){
	int s=0;
	int f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=5e4,P=998244353;


int n;
int s[N],a[N],sum;
int dp[110][N][2]; // 背包表示p之和为i，有j个不同的方案数
ll Inv[N]; 
ll c;

ll qpow(ll x,ll k) {
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
} 



int main(){
	freopen("switch.in","r",stdin),freopen("switch.out","w",stdout);
	n=rd();
	rep(i,1,n) s[i]=rd();
	dp[0][0][0]=1;
	rep(i,1,n) {
		int x=rd();
		rep(j,0,sum) rep(k,0,1) rep(d,0,1) 
			dp[i][j+d*x][k^(d&&s[i])]=(dp[i][j+d*x][k^(d && s[i])]+dp[i-1][j][k])%P;
		sum+=x;
	}
	Inv[0]=Inv[1]=1;
	rep(i,2,sum) Inv[i]=(P-P/i)*Inv[P%i]%P;
	ll ans=0;
	rep(i,1,sum) ans=(ans+Inv[i]*dp[n][i][1])%P; // 因为最后统计的时候没有空集，所以i从1开始
	printf("%lld\n",ans*sum%P);
}