题解 P3211 【[HNOI2011]XOR和路径】

花里心爱 · 2019-03-20 07:51:03 · 题解

题目链接

一般来说，遇到求期望的题时，我们都要转化期望的形式使其便于求解。

对于这道题，我们可以将它转化为一个期望dp模型。

我们先试着列一下dp式子：

设f[i]为当前在i号节点，走到n号节点得到的异或和的期望值。

然后对于每个f[i]，它可以由每个与它相邻的节点的状态转移过来。所以状态转移方程为：

（这里p表示与i相邻的边，to[p]为这条边连接的另一个点，val[p]为边权，deg[i]表示i的度）

然后我们就可以愉快地转移……了吗？

由于这个图不是一个DAG，所以通过一个点可能经过某条路径使它能够回到原点。也就是说，这里的状态是有后效性的。

看起来状态有后效性的题我们似乎并不能dp求解。

然而这里的答案（期望）显然是存在的。

于是我们设所有的f[i]为未知数，根据上面的式子列方程求解。

我们把原式转化一下：

（其中所有的f为未知量）

我们需要用到高斯消元，时间复杂度为O(n^3)

然后我们就会发现，上面列的dp式子带一个\operatorname{xor}，不能直接用这个式子列方程。

于是我们就考虑期望的各种神奇的性质（好吧我们知道的关于期望的性质只有一个，那就是期望具有线性性，即E(a+b) = E(a) + E(b)）

那么由于异或运算的每一位互不影响，我们可以把每一位拆开。这样我们的val[p]就只剩下了0或1。

然后我们的f[i]定义就变成了：当前在i号节点，走到n号节点得到的异或和为1的期望值（也就是该位为1的概率）。

然后我们就能把\operatorname{xor}拆成两种情况，即：

（因为1\operatorname{xor}0=0\operatorname{xor}1=1）

对于每一位都做一遍，最终答案为\sum_{i=0}^{30}{2^if[1]}

时间复杂度为O(30n^3)

下面放代码：

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define maxn 105
#define maxm 20005
inline int read() {
    int d=0;char ch=getchar();while(!isdigit(ch))ch=getchar();
    while(isdigit(ch)){d=d*10+ch-48;ch=getchar();}return d;
}

const double eps = 1e-9;
inline double fabs(double x) {return x < 0 ? -x : x;}
inline int sgn(double x) {return x > eps ? 1 : x < -eps ? -1 : 0;}

int n, m, u, v, w;
int head[maxn], ver[maxm], edge[maxm], nxt[maxm], tot;
int deg[maxn];

inline void add(int u, int v, int w) {
    ver[++tot] = v, edge[tot] = w, nxt[tot] = head[u], head[u] = tot;
}

double a[maxn][maxn];
double ans;

void gauss() { // 高斯消元过程
    double div;
    for(int i = 1; i <= n; ++i) {
        int m = i;
        for(int j = i+1; j <= n; ++j)
            if(sgn(fabs(a[j][i])-fabs(a[m][i])) == 1)
                m = j;
        for(int k = i; k <= n+1; ++k)
            std::swap(a[m][k], a[i][k]);
        div = a[i][i];
        for(int k = i; k <= n+1; ++k)
            a[i][k] /= div;
        for(int j = 1; j <= n; ++j) {
            if(j != i) {
                div = a[j][i];
                for(int k = i; k <= n+1; ++k)
                    a[j][k] -= div*a[i][k];
            }
        }
    }
}

int main() {
    n = read(), m = read();
    for(int i = 1; i <= m; ++i) {
        u = read(), v = read(), w = read();
        if(u == v) { // 注意有自环的情况，此时只能统计一次
            ++deg[u];
            add(u, v, w);
        }
        else {
            ++deg[u], ++deg[v];
            add(u, v, w), add(v, u, w);
        }
    }
    for(int k = 30; k >= 0; --k) { // 对于每一位拆开来做
        memset(a, 0, sizeof(a));
        for(int i = 1; i < n; ++i) {
            a[i][i] = -deg[i];
            for(int p = head[i]; p; p = nxt[p]) {
                int v = ver[p], w = (edge[p]>>k)&1; // w为边权在2进制下的第k位
                if(w) a[i][v] -= 1, a[i][n+1] -= 1;
                else a[i][v] += 1; 
            }
        }
        a[n][n] = 1;
        gauss();
        ans += (1<<k)*a[1][n+1]; // 合并答案
    }
    printf("%.3lf", ans);
    return 0;
}