「ZJOI2019」开关

Posted on Edited on In

「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^S]F'(x)=-\frac{2^n}{1-\sum_{i\notin S}p_i+\sum_{i\in S}p_i}=-\frac{2^n}{2\sum_{i\in S}p_i}\]

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

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

\[[x^\empty]F'(x)-\sum_{S\ne \empty}\frac{2^n}{2\sum_{i\in S}p_i}=0\]

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

\[[x^S]F(x)=2^{-n}\cdot \sum_T(-1)^{|S\cap T|}[x^T]F'(x)\]

\[=2^{-n}([x^\empty]F'(x)+\sum_{T\ne \empty}(-1)^{|S\cap T|}[x^T]F'(x))\]

\[=\sum_{T\ne\empty}\frac{1}{2\sum_{i\in T}p_i}+2^{-n}\sum_{T\ne \empty}(-1)^{|S\cap T|}[x^T]F'(x)\]

\[=\sum_{T\ne \empty,|S\cap T|\mod 2=1} \frac{1}{\sum_{i\in T} p_i}\]

下面是一个背包，跑的同时统计一下就好了 \(|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);
}