CC 采用 $\text{CC BY-NC-SA 4.0}$ 许可,转载请注明:“转自 AGC034F RNG and XOR”
以上为阅读本文章的前置知识,而并非解决本题必备知识。
本文取材自上述两篇博客/讲义/文章。
有趣的是,$0x=0$ 在其他题目中是烦人的 edge case,在本题中反而成为了突破口。
#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pi;
typedef long long LL;
const int P = 998244353;
const int INF = 0x3f3f3f3f;
const LL INFLL = 0x3f3f3f3f3f3f3f3fll;
const int N = 1e6 + 1e5;
int n, m, inv_n;
LL a[N], b[N], c[N], S, inv_S;
inline LL ksm(LL base, LL x) {
LL res = 1;
while(x) {
if(x & 1) res *= base, res %= P;
x >>= 1, base *= base, base %= P;
}
return res;
}
inline void fwt_xor(LL a[], int type) {
for(int i = 1; i < n; i <<= 1)
for(int j = 0; j < n; j += i << 1)
for(int k = j; k < j + i; k++)
a[k] = (a[k] + a[k + i]) % P,
a[k + i] = (a[k] - a[k + i] * 2 + P * 2) % P;
if(type == -1)
for(int i = 0; i < n; i++) a[i] = (a[i] * inv_n) % P;
}
void init() {
int len;
cin >> len;
n = 1 << len;
inv_n = ksm(n, P - 2);
for(int i = 0; i < n; i++) scanf("%lld", &a[i]), S = (S + a[i]) % P;
inv_S = ksm(S, P - 2);
for(int i = 0; i < n; i++) a[i] = (a[i] * inv_S) % P;
fwt_xor(a, 1);
for(int i = 0; i < n; i++) b[i] = c[i] = 1;
b[0] = 0;
fwt_xor(b, 1), fwt_xor(c, 1);
for(int i = 0; i < n; i++) c[i] = (c[i] - b[i] + P) % P;
LL x = (P - b[0]) * ksm(c[0], P - 2) % P;
for(int i = 0; i < n; i++) c[i] = (b[i] + c[i] * x) % P;
for(int i = 0; i < n; i++) {
LL tmp = ksm((1 - a[i] + P) % P, P - 2);
c[i] = (c[i] * tmp) % P;
}
for(int i = 0; i < n; i++) b[i] = c[i];
c[0] = 1;
fwt_xor(b, -1), fwt_xor(c, -1);
for(int i = 0; i < n; i++) c[i] = (c[i] - b[i] + P) % P;
x = (P - b[0]) * ksm(c[0], P - 2) % P;
for(int i = 0; i < n; i++) c[i] = (b[i] + c[i] * x) % P;
for(int i = 0; i < n; i++) printf("%lld\n", c[i]);
}
int main() {
init();
return 0;
}
Author : Fanfaredash