BZOJ-2337 XOR和路径（HNOI2011）概率DP+概率的线性叠加

题意：给出n个点和m条边，每条边有权值wi，从1出发，每次等概率选一条出边走，直到终点n停止，得到的值是路径所有边的异或和。问异或和期望。

解法：这道题非常有意思！首先比较直观的想法就是dp[x]代表x走到终点n的期望异或和。那么容易写出状态转移方程dp[x]=sigma(dp[y]^w)/du[x] (y是x出点，w是出边权值)。虽然有自环和环，但是我们可以用高斯消元解决。但是再仔细一看，有xor还有除法的方程怎么用高斯消元解。。。

于是我们又想到期望是有线性叠加性的E(x+y)=E(x)+E(y)。那么此题又涉及到位运算，于是我们按位考虑！

例如考虑二进制第k位，dp[x]代表x到终点n的异或和结果第k位为1的期望，因为此时只涉及到0和1了，于是我们就可以愉快地加减了。

dp[x]=( sigma(dp[y])+sigma(1-dp[y]) ) / du[x] 。前面一项代表边w的第k位为0于是我们要在y上找1的概率，后面一项代表边w的第k位为1于是我们就要在y找0的概率。

写出转移方程之后基本功扎实就很容易化简然后上高斯消元解方程了。

最后我们把各个位的贡献线性叠加即可。

代码如下：

#include<bits/stdc++.h>

using namespace std;

const int N=+;

const int M=1e4+;

const long double eps=1e-;

int n,m,du[N];

int cnt=,head[N],nxt[M<<],to[M<<],len[M<<];

void add_edge(int x,int y,int z) {

    nxt[++cnt]=head[x]; to[cnt]=y; len[cnt]=z; head[x]=cnt;

}

long double c[N][N],b[N];

void Gauss(int n,int m) {  //变量个数 方程个数

    int r=;

    for (int i=;i<=n;i++) {

        int j=r+;

        while (j<=m && fabs(c[j][i])<eps) j++;  //从下面方程找一个第i位不为0的

        if (j==m+) continue;  //不存在第i位不为0的方程

        r++;  //矩阵的秩

        for (int k=;k<=n;k++) swap(c[r][k],c[j][k]);  //存在第i位不为0的方程，交换上去

        swap(b[r],b[j]);

        for (int j=;j<=m;j++) {  //以r方程回代m个方程

            if (r==j) continue;

            long double rate=c[j][i]/c[r][i];

            for (int k=i;k<=n;k++) c[j][k]-=c[r][k]*rate;

            b[j]-=b[r]*rate;

        }

    }

    for (int i=;i<=n;i++) b[i]=b[i]/c[i][i];  //唯一解求解

}

int main()

{

    cin>>n>>m;

    for (int i=;i<=m;i++) {

        int x,y,z; scanf("%d%d%d",&x,&y,&z);

        add_edge(x,y,z);

        if (x!=y) add_edge(y,x,z);

        if (x==y) du[x]++; else du[x]++,du[y]++;

    }

    long double ans=;

     for (int k=;k<;k++) {

        memset(c,,sizeof(c));

        memset(b,,sizeof(b));

        for (int i=;i<n;i++) {  //建立方程

            for (int j=head[i];j;j=nxt[j]) {

                int t=len[j];

                if ((t&(<<k))==) {

                    c[i][to[j]]-=(long double)1.0/du[i];

                } else {

                    c[i][to[j]]+=(long double)1.0/du[i];

                    b[i]+=(long double)1.0/du[i];

                }

            }

            c[i][i]+=1.0;

        }

        c[n][n]=1.0;

        Gauss(n,n);

        ans+=b[]*(<<k);

    }

    printf("%.3Lf\n",ans);

    return ;

}

巴特西

BZOJ-2337 XOR和路径（HNOI2011）概率DP+概率的线性叠加

最新文章

热门文章