# xht37 的洛谷博客

xht37's blog：https://www.xht37.com/

# 请在博客中查看

## OI 中的运用

### 或

$$c_{i}=\sum_{i=j | k} a_{j} b_{k}$$

\begin{aligned} fwt[a] \times fwt[b] &= \left(\sum_{j|i=i} a_j\right)\left(\sum_{k|i=i} b_k\right) \\\\ &= \sum_{j|i=i} \sum_{k|i=i} a_jb_k \\\\ &= \sum_{(j|k)|i = i} a_jb_k \\\\ &= fwt[c] \end{aligned}

#### $a \to fwt[a]$

inline void OR(modint *f) {
for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
for (int i = 0; i < n; i += o)
for (int j = 0; j < k; j++)
f[i+j+k] += f[i+j];
}

#### $fwt[a] \to a$

inline void IOR(modint *f) {
for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
for (int i = 0; i < n; i += o)
for (int j = 0; j < k; j++)
f[i+j+k] -= f[i+j];
}

inline void OR(modint *f, modint x = 1) {
for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
for (int i = 0; i < n; i += o)
for (int j = 0; j < k; j++)
f[i+j+k] += f[i+j] * x;
}

### 与

inline void AND(modint *f, modint x = 1) {
for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
for (int i = 0; i < n; i += o)
for (int j = 0; j < k; j++)
f[i+j] += f[i+j+k] * x;
}

### 异或

\begin{aligned} fwt[a] \times fwt[b] &= \left(\sum_{i\otimes j = 0} a_j - \sum_{i\otimes j = 1} a_j\right)\left(\sum_{i\otimes k = 0} b_k - \sum_{i\otimes k = 1} b_k\right) \\ &=\left(\sum_{i\otimes j=0}a_j\right)\left(\sum_{i\otimes k=0}b_k\right)-\left(\sum_{i\otimes j=0}a_j\right)\left(\sum_{i\otimes k=1}b_k\right)-\left(\sum_{i\otimes j=1}a_j\right)\left(\sum_{i\otimes k=0}b_k\right)+\left(\sum_{i\otimes j=1}a_j\right)\left(\sum_{i\otimes k=1}b_k\right) \\ &=\sum_{i\otimes(j \operatorname{xor} k)=0}a_jb_k-\sum_{i\otimes(j\operatorname{xor} k)=1}a_jb_k \\ &= fwt[c] \end{aligned}

\begin{aligned} fwt[a] &= \text{merge}(fwt[a_0] + fwt[a_1], fwt[a_0] - fwt[a_1]) \\\\ a &= \text{merge}(\frac{a_0 + a_1}2, \frac{a_0 - a_1}2) \end{aligned}

inline void XOR(modint *f, modint x = 1) {
for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
for (int i = 0; i < n; i += o)
for (int j = 0; j < k; j++)
f[i+j] += f[i+j+k],
f[i+j+k] = f[i+j] - f[i+j+k] - f[i+j+k],
f[i+j] *= x, f[i+j+k] *= x;
}

### 【模板】P4717 【模板】快速沃尔什变换

const int N = 1 << 17 | 1;
int n, m;
modint A[N], B[N], a[N], b[N];

inline void in() {
for (int i = 0; i < n; i++) a[i] = A[i], b[i] = B[i];
}

inline void get() {
for (int i = 0; i < n; i++) a[i] *= b[i];
}

inline void out() {
for (int i = 0; i < n; i++) print(a[i], " \n"[i==n-1]);
}

inline void OR(modint *f, modint x = 1) {
for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
for (int i = 0; i < n; i += o)
for (int j = 0; j < k; j++)
f[i+j+k] += f[i+j] * x;
}

inline void AND(modint *f, modint x = 1) {
for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
for (int i = 0; i < n; i += o)
for (int j = 0; j < k; j++)
f[i+j] += f[i+j+k] * x;
}

inline void XOR(modint *f, modint x = 1) {
for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
for (int i = 0; i < n; i += o)
for (int j = 0; j < k; j++)
f[i+j] += f[i+j+k],
f[i+j+k] = f[i+j] - f[i+j+k] - f[i+j+k],
f[i+j] *= x, f[i+j+k] *= x;
}

int main() {
rd(m), n = 1 << m;
for (int i = 0; i < n; i++) rd(A[i]);
for (int i = 0; i < n; i++) rd(B[i]);
in(), OR(a), OR(b), get(), OR(a, P - 1), out();
in(), AND(a), AND(b), get(), AND(a, P - 1), out();
in(), XOR(a), XOR(b), get(), XOR(a, (modint)1 / 2), out();
return 0;
}

2019-12-11 03:10:04 in 题解