XSY 2250 - 生日礼物 & HNOI 2013 - 游走 & BZOJ 3207 - 博物馆

专题练习 题目 高斯消元 概率论

总结: 高斯消元

1. 高斯消元的3个问题
① 有没有解: 考虑不含系数的一行, 若该行的结果非0, 那么无解.
② 有多少个解: $m^{自由元个数}$
③ 求解: 回溯的时候考虑搜索, 初次的消元不要搜索.
2. 正确姿势

int Free(void) {
    int cnt=0;
    F(i,1,ind) {
        if (!a[i][i]) F(j,i+1,ind) if (a[j][i]) { swap(a[i],a[j]); break; }
        if (!a[i][i]) { cnt++; continue; }
        F(j,i+1,ind) if (a[j][i]) a[j]=a[j]^a[i];
    }
    return cnt;
}

不变的地方: 第 $i$ 个未知数放在第 $i$ 行.
变化的地方:
① 消不消掉上面的
② 消的方法(逆元, 直接除, 辗转)
③ 交换的方法(浮点数取最小)
④ 对于异或方程, 可以使用 bitset 进行优化.

3. 相关方法
常用于 行列式求值 , 矩阵求逆 , 线性基 , 解方程 .
对于棋盘的问题, 通常只要设部分的未知数, 然后递推求解其他的未知数.

XSY 2250 - 生日礼物

题意

  $n\times m$ 的开关, 最初全部都没有亮. 每按一个开关, 能将 $|x_1-x_2|+|y_1-y_2|=5$ 的所有位置的状态取反.
  求有多少种方法, 能将所有的灯亮.
  $1\le n,m\le 600$

分析

  暴力的想法: 设 $n\times m$ 个未知数, 高斯消元.
  高斯消元可以求出自由元的个数 $s$ , 然后答案为 $2^s$ .
  但是 $O((nm)^3)$ 显然会 TLE .

  注意到这是一个棋盘, 我们假如能知道第一行, 第二行, 第一列的所有状态.
  对于另外的一个状态$(x,y)$ , 我们可以通过 $(x-2,y-1)$ 推出 $(x,y)$ . 此时 $(x-2,y-1)$ 一定有解, 相当于把 $(x-2,y-1)$ 变成了 $(x,y)$ .
  那么最终考虑后两行, 以及后一列的所有状态即可. 这样我们需要设的状态数就是 $O(n)$ 的了.
  Update: 更本质的理解是设 $n\times m$ 个未知数, 进行了 $O(n\times m)$ 次代入, 最后剩下的就是最后的两行, 以及最后的一列.

  发现依然过不了, 由于它是异或方程, 只有 0 和 1 , 所以我们考虑使用 bitset 进行优化.

  经打表找规律发现, 该问题一定有解. 所以不需要存储异或和, 只需要系数矩阵即可.

实现

#include <cstdio>
#include <algorithm>
#include <utility>
#include <bitset>
using namespace std;
#define F(i,a,b) for (int i=(a);i<=(b);i++)
const int N=605;
const int L=1850;
const int dx[9]={ -2 , -2 , -1 , -1 ,  0 ,  1 ,  1 ,  2 ,  2 };
const int dy[9]={ -1 ,  1 , -2 ,  2 ,  0 , -2 ,  2 , -1 ,  1 };
int n,m;
bitset<L> s[N][N]; int tot;
bitset<L> a[L]; int ind;
inline int check(int x,int y) { return 1<=x&&x<=n&&1<=y&&y<=m; }
int Free(void) {
    int cnt=0;
    F(i,1,ind) {
        if (!a[i][i]) F(j,i+1,ind) if (a[j][i]) { swap(a[i],a[j]); break; }
        if (!a[i][i]) { cnt++; continue; }
        F(j,i+1,ind) if (a[j][i]) a[j]=a[j]^a[i];
    }
    return cnt;
}
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("present.in","r",stdin);
        freopen("present.out","w",stdout);
    #endif
    scanf("%d%d",&n,&m); if (n==1) return printf("1\n"),0;
    F(i,1,2) F(j,1,m) s[i][j][++tot]=1;
    F(i,3,n) s[i][1][++tot]=1;
    F(i,3,n) F(j,2,m) {
        int x=i-2,y=j-1;
        F(k,0,8) {
            int _x=x+dx[k],_y=y+dy[k];
            if (check(_x,_y)&& (_x!=i||_y!=j) )
                s[i][j]=s[i][j]^s[_x][_y];
        }
    }
    pair<int,int> go[L];
    F(i,n-1,n) F(j,1,m) go[++ind]=make_pair(i,j);
    F(i,1,n-2) go[++ind]=make_pair(i,m);
    F(i,1,ind) {
        int x=go[i].first,y=go[i].second;
        F(k,0,8) {
            int _x=x+dx[k],_y=y+dy[k];
            if (check(_x,_y))
                a[i]=a[i]^s[_x][_y];
        }
    }
    int t=Free();
    int mul=1; F(i,1,t) mul=(mul+mul)%123456789; printf("%d\n",mul);
    return 0;
}

HNOI 2013 - 游走

题意

  无向简单图， $n$ 个点， $m$ 条边。
  从点 $1$ 出发，等概率选边走到点 $m$ 。
  给边进行编号，使得从 $1$ 走到 $m$ 的路径上的边的编号之和的期望值最小。
  $1\leq n\leq 500$

分析

  https://blog.sengxian.com/solutions/bzoj-3143

实现

#include <cstdio>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <functional>
using namespace std;
#define F(i,a,b) for (int i=(a);i<=(b);i++)
const int N=505;
int n,m; int d[N],tot,hd[N]; struct Edge { int v,nx; inline Edge(int _v=0,int _nx=0):v(_v),nx(_nx){} }mp[500005];
double f[N][N]; double ans[N];
double cnt[250005],sum;
inline int rd(void) {
    int x=0,f=1; char c=getchar();
    for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
    for (;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
inline void Ins(int u,int v) {
    mp[++tot]=Edge(v,hd[u]); hd[u]=tot; d[u]++;
    mp[++tot]=Edge(u,hd[v]); hd[v]=tot; d[v]++;
}
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("sdchr.in","r",stdin);
    #endif
    tot=1; n=rd(),m=rd(); F(i,1,m) { int u=rd(); Ins(u,rd()); }
    F(p,1,n) {
        f[p][p]=1; f[p][n+1]=(p==1);
        for (int k=hd[p];k>0;k=mp[k].nx) if (mp[k].v!=n)
            f[p][mp[k].v]=-1.0/d[mp[k].v];
    }
    F(i,1,n) {
        if (f[i][i]==0) {
            int id=i+1; F(j,i+2,n) if (fabs(f[j][i])>fabs(f[id][i])) id=j;
            F(k,1,n+1) swap(f[i][k],f[id][k]);
        }
        F(j,1,n) if (i!=j&&f[j][i]!=0) {
            double t=f[j][i]/f[i][i];
            F(k,i,n+1) f[j][k]=f[j][k]-t*f[i][k];
        }
    }
    F(i,1,n) ans[i]=f[i][n+1]/f[i][i];
    F(p,1,n-1) for (int k=hd[p];k>0;k=mp[k].nx)
        cnt[k>>1]+=ans[p]/d[p];
    sort(cnt+1,cnt+m+1,greater<double>());
    F(i,1,m) sum+=i*cnt[i]; printf("%0.3lf\n",sum);
    return 0;
}

BZOJ 3270 - 博物馆

题意

  给定一张 $N$ 个点, $M$ 条边的无向图. 给定 $A$ 和 $B$ 的初始位置. 每次 $A$ 和 $B$ 会进行随机游走, 相遇的时候停下. 问 $A$ 和 $B$ 在每个点相遇的概率.
  $1\le N\le 20, 1\le M\le \frac{n(n+1)}{2}$

分析

  由于 $A$ 和 $B$ 相遇就停止, 所以 每个点相遇的期望次数 = 1次 * 每个点相遇的概率 . 我们考虑求出 $f[i][i]$ : $A$ 和 $B$ 在第 $i$ 个点相遇的期望次数.
  那么, 对于起点, $f[a][b]=1+\sum f[pa][pb]\times p$ , 对于其他点, $f[a][b]=\sum f[pa][pb]$ .
  高斯消元即可.