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\limits_{j=0}^{2^n-1}f_{i\oplus j}p_j\)
\(F+f’_0=I+F*P\)
\(I=\sum\limits_{i=0}^{2^n-1}x^i\)
求 \(f’_0\):
\(F=\sum\limits_{i=0}^{\infty}f_ix^i\)
\(S(F)=\sum\limits_{i=0}^{\infty} f_i\)
\(S(F)+f’_0=S(I)+S(F)*S(P)\)
\(S(P)=1,S(I)=2^n\)
\(f_0’=2^n\)
\(F+2^n=I+F*P\)
\(F(P-1)=2^n-I,F=\dfrac{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<cstdio>
#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;
}
原文地址:http://www.cnblogs.com/Sakura-TJH/p/luogu_AGC034F.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性