[笔记] RNG and XOR

最初 $x=0$,每一次操作以 $p_i$ 概率选择 $i$ 并将 $x$ 设为 $x\otimes i$(异或),问对于所有 $k$ ($1\le k\le 2^n$)期望操作多少次能第一次变成 $k$。

$1\le n\le 18$

题目链接


思路

一眼出式子:
$$
f_i=1+\sum_v p_v\cdot f_{v\otimes i}
$$
其中 $f_0=0$。然后只会 $O\left(\left(2^n\right)^3\right)$ 高斯消元了,显然过不了。

注意到异或,我们来考虑 FWT。有下面的式子:

$$ \left[f_0,f_1,f_2,\cdots\right]\otimes\left[p_0,p_1,p_2,\cdots\right]\\ =[?,f_1-1,f_2-1,f_3-1,\cdots] $$

这里的乘法是 FWT 异或卷积。$?$ 的取值是未定义的,因为我们规定了 $f_0$ 等于 0,但是实际乘法乘出来的东西不一定是这个。

考虑一下发现 $?$ 应该是 $(f_0+2^n-1)$,因为卷积之后新序列的和是等于原来两个序列的和的积的,又因为 $\sum_i p_i=1$,所以可以推出来。

现在一个等式两个未知还是没法搞,考虑弄掉右边。我们发现

$$ \begin{aligned} c_k&=\sum_{i\otimes j=k}a_i\cdot b_j\\ &=a_k\cdot b_0+\sum_{i\otimes j=k,j\ne0}a_i\cdot _j \end{aligned} $$

我们把 $b_0$ 减个 1 可以对于每个 $i$ 把 $c_i$ 削掉 $a_i$,然后就有:

$$ \left[f_0,f_1,f_2,\cdots\right]\otimes\left[p_0-1,p_1,p_2,\cdots\right]\\ =[2^n-1,-1,-1,\cdots] $$

然后就是 $A\otimes B=C$,$A=C\otimes B^{-1}$ 的形式了,FWT 求逆带走。FWT 的指数是模意义下的,所以本身就是循环卷积,FWT 后求逆元然后再 FWT 回去就是 FWT 求逆。

有个小问题。因为 FWT 后第 0 项是序列所有元素之和,因此中间那个 FWT 后第 0 项是 0,右边那个也是,导致我们没法反推出左边的 FWT 第 0 项到底是什么。实际做的时候,我们是直接 $a_i=c_i\cdot b_i^{-1}$ 次方,算的是 $a_0=0$ 了,但实际上并不对。我们注意到,$f_0$ 对左边的 FWT 每一项都贡献了一个 $f_0$,所以我们改变了 $f_0$ 的值对其它项的影响是线性且系数为 1 的,所以我们每一项都减一个 $f_0$ 就好了。

也就是说,在下面的代码里面加一个 w[0] = rand() % mod; 对计算过程没有任何影响。

代码

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
// Mivik 2020.12.25
#include <mivik.h>

#include <tuple>

MI cin;

typedef long long qe;

const int $n = 18;
const int $s = 1 << $n;
const int mod = 998244353;

int n, L, W;
int v[$s], w[$s];
inline int pro(int x) { return x >= mod? x - mod: x; }
inline int per(int x) { return x < 0? x + mod: x; }
inline qe ksm(qe x, int p = mod - 2) {
qe ret = 1;
for (; p; p >>= 1, (x *= x) %= mod) if (p & 1) (ret *= x) %= mod;
return ret;
}
inline int div2(int x) { return ((x & 1)? x + mod: x) >> 1; }
template<bool rev>
inline void fwt(int *v) {
for (int i = 1, q = 2; i < L; q = (i = q) << 1)
for (int j = 0; j < L; j += q)
for (int k = 0; k < i; ++k) {
int &x = v[j | k], &y = v[i | j | k];
std::tie(x, y) = std::make_tuple(
pro(x + y),
per(x - y)
);
}
if (!rev) return;
for (int i = 0; i < L; ++i)
v[i] = (qe)v[i] * W % mod;
}
int main() {
cin > n; W = ksm(L = 1 << n);
int sum = 0;
for (int i = 0; i < L; ++i)
sum = pro(sum + (v[i] = R));
sum = ksm(sum);
for (int i = 0; i < L; ++i) {
v[i] = (qe)v[i] * sum % mod;
w[i] = mod - 1;
}
w[0] = L - 1;
v[0] = per(v[0] - 1);
fwt<0>(w); fwt<0>(v);
for (int i = 0; i < L; ++i)
w[i] = (qe)w[i] * ksm(v[i]) % mod;
// w[0] = rand() % mod;
fwt<1>(w);
for (int i = 0; i < L; ++i)
cout < per(w[i] - w[0]) < endl;
}
作者

Mivik

发布于

2020-12-25

更新于

2021-05-31

许可协议

评论