社区讨论

这个代码为什么是对的？

AAugust_Light
P3175[HAOI2015] 按位或参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@m6brnuk8
此快照首次捕获于
2025/01/25 13:44
去年
此快照最后确认于
2025/11/04 10:41
4 个月前
查看原帖
凭直觉做的过了，但是实际上并没有搞清楚为什么是对的。
设了一个数组 EE，满足关系 Ek=[k=0]+∑i∪j=kEi×pjE_k = [k=0] + \sum\limits_{i \cup j = k} E_i \times p_j，本题答案为 ∑i=02n−2Ei\sum\limits_{i=0}^{2^n-2} E_i（E2n−1E_{2^n-1} 必为 ∞\infty，不加上）
这个关系式可以用 FMT 写成 E^=E^⋅P^+1\hat E = \hat E \cdot \hat P + 1，其中 E^\hat E 表示 EE 数组的莫比乌斯变换，P^\hat P 表示 pp 数组的莫比乌斯变换，⋅\cdot 表示对应位置直接相乘。
解方程得 E^=11−P^\hat E = \frac 1 {1 - \hat P}（除法为对应位置直接相除而不是多项式求逆）。
因此先把 pp 做个 FMT，把 E^\hat E 算出来再 IFMT 回去。
但是我其实到现在也没搞明白我设的 EE 是个啥。求教。
CPP
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, r, l) for (int i = (r); i >= (l); i--)
using namespace std;
typedef long long ll;

const int MAXN = (1 << 20) + 5;

int n, tot;
double p[MAXN], E[MAXN];

void FMT(double a[]) {
    rep(i, 0, n)
        rep(u, 0, tot)
            if (u >> i & 1)
                a[u] += a[u ^ (1 << i)];
}
void invFMT(double a[]) {
    rep(i, 0, n)
        rep(u, 0, tot)
            if (u >> i & 1)
                a[u] -= a[u ^ (1 << i)];
}

int main() { ios::sync_with_stdio(0); cin.tie(0);
    cin >> n, tot = (1 << n) - 1;
    rep(u, 0, tot)
        cin >> p[u];

    FMT(p);
    rep(u, 0, tot)
        E[u] = 1 / (1 - p[u]);
    invFMT(E);
    double ans = 0;
    rep(u, 0, tot-1)
        ans += E[u];
    if (isinf(ans))
        cout << "INF" << '\n';
    else
        cout << fixed << setprecision(10) << ans << '\n';

    return 0;
}

回复

共 1 条回复，欢迎继续交流。

正在加载回复...