【luogu AGC034F】RNG and XOR（FWT）

RNG and XOR

题目链接：luogu AGC034F

题目大意

给你一个长度为 2^n 的数组 A。
一开始有一个 $0$ 数，然后每次你随机给它异或上 0~2^n-1 中的数，随机到 $i$ 的概率跟 Ai+1 成正比。
然后对于 0~2^n-1 每个数问你第一次变成这个数的期望异或次数。

思路

考虑使用生成函数，$f_i$ 为答案。

$f_0=0$
$f_i=1+\sum _{j=0}^{2^n-1}{f}_{i\oplus j}{p}_j$
$F+f_0^{\prime }=I+F\ast P$

$I=\sum _{i=0}^{2^n-1}{x}^i$

求 $f_0^{\prime }$：
$F=\sum _{i=0}^{\infty }{f}_i{x}^i$
$S(F)=\sum _{i=0}^{\infty }{f}_i$
$S(F)+f_0^{\prime }=S(I)+S(F)\ast S(P)$
$S(P)=1,S(I)=2^n$
$f_0^{\prime }=2^n$

$F+2^n=I+F\ast P$
$F(P-1)=2^n-I,F=\frac{2^n-I}{P-1}$

但是有一个问题就是 $[x^0](P-1)$ 它 FWT 之后会是 $0$。
那就别管第 $0$ 位，当他是 $0$ 然后 IFWT。
那我们还有一个限制条件是 $f_0=0$，那你 IFWT 之后 $0$ 会赋值到的位置是所有，但你现在没有了，那你 $f_0$ 现在的值是 $-x$，那你给所有位置的值都加上 $x$，就相当于处理了 $0$ 位置的贡献了。

代码

#include
#define ll long long
#define mo 998244353

using namespace std;

const int N = 1 << 18;
int n;
ll p[N], a[N], sum, I[N], f[N], inv2;

ll ksm(ll x, ll y) {
	ll re = 1;
	while (y) {
		if (y & 1) re = re * x % mo;
		x = x * x % mo; y >>= 1;
	}
	return re;
}

void FWT(ll *f, int n, int op) {
	for (int mid = 1; mid < n; mid <<= 1)
		for (int R = (mid << 1), j = 0; j < n; j += R)
			for (int k = 0; k < mid; k++) {
				ll x = f[j | k], y = f[j | mid | k];
				if (op == 1) {
					f[j | k] = (x + y) % mo;
					f[j | mid | k] = (x - y + mo) % mo;
				}
				else {
					f[j | k] = (x + y) * inv2 % mo;
					f[j | mid | k] = (x - y + mo) * inv2 % mo;
				}
			}
}

int main() {
	inv2 = (mo + 1) / 2;
	
	scanf("%d", &n);
	for (int i = 0; i < (1 << n); i++) scanf("%lld", &a[i]), (sum += a[i]) %= mo;
	sum = ksm(sum, mo - 2); for (int i = 0; i < (1 << n); i++) p[i] = a[i] * sum % mo;
	
	p[0] = (p[0] - 1 + mo) % mo;
	I[0] = (1 << n); for (int i = 0; i < (1 << n); i++) I[i] = (I[i] - 1 + mo) % mo;
	
	FWT(p, 1 << n, 1); FWT(I, 1 << n, 1);
	for (int i = 1; i < (1 << n); i++) f[i] = I[i] * ksm(p[i], mo - 2) % mo;
	FWT(f, 1 << n, -1);
	
	ll fix = f[0];
	for (int i = 0; i < (1 << n); i++) f[i] = (f[i] - fix + mo) % mo;
	for (int i = 0; i < (1 << n); i++) printf("%lld\n", f[i]);
	
	return 0;
}
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