【LOJ】#2290. 「THUWC 2017」随机二分图-白红宇

【LOJ】#2290. 「THUWC 2017」随机二分图

阅读量：4354 次

发布时间：2019-06-07

本文共 3177 字，大约阅读时间需要 10 分钟。

题解

看了一眼觉得是求出图对图统计完美匹配的个数（可能之前做过这样模拟题弃疗了，一直心怀恐惧。。。

然后说是统计一下每种匹配出现的概率，也就是，当前左边点匹配状态为S，右边点匹配状态为T，每种匹配出现的概率的总和作为\(f[S][T]\)，我们需要的就是\(f[2^{n} - 1][2^{n} - 1]\)

然而，会发现转移起来似乎非常麻烦,例如，假如两条边一起出现，各自匹配出现的概率是多少？

我们把每组边拆开，变成每条边在匹配中有50%概率出现，一组边同时在匹配中出现的概率是25%，如果t = 2,那么概率就是-25%

为什么呢，对于t = 1的边，两条肯定一起出现，那么如果我们算第一条边进入匹配，概率是50%，算第二条边进入匹配，概率也是50%，但是由于两条边一起出现的特殊性质，我们按照这个方法算，如果两个匹配都出现的概率是25%，但是两条匹配都出现的概率是50%，我们就加上一个25%两条边一起匹配

同理，对于t = 2的边，第一条边进去匹配是50%，第二条边进入匹配是50%，然而两条边一起进入匹配是不可能的，只有减掉那25%的概率了

代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          //#define ivorysi#define pb push_back#define space putchar(' ')#define enter putchar('\n')#define mp make_pair#define pb push_back#define fi first#define se second#define mo 974711using namespace std;typedef long long int64;typedef double db;template
           
            void read(T &res) { res = 0;char c = getchar();T f = 1; while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { res = res * 10 + c - '0'; c = getchar(); } res *= f;}template
            
             void out(T x) { if(x < 0) {putchar('-');x = -x;} if(x >= 10) { out(x / 10); } putchar('0' + x % 10);}const int MOD = 1000000007;int N,M,tot,fir[(1 << 15) + 1];struct Edge{ int a[2],b[2],val;}E[10005];vector
             
               MK[20];map
              
                f[(1 << 15) + 5];int fpow(int x,int c) { int res = 1,t = x; while(c) { if(c & 1) res = 1LL * res * t % MOD; t = 1LL * t * t % MOD; c >>= 1; } return res;}void Init() { read(N);read(M); int t,a0,a1,b0,b1; int Inv2 = (MOD + 1) / 2,Inv4 = 1LL * Inv2 * Inv2 % MOD; for(int i = 1 ; i <= M ; ++i) { read(t);read(a0);read(b0); if(t == 0) { E[++tot].a[0] = a0;E[tot].b[0] = b0;E[tot].val = Inv2; MK[a0].pb(tot); } else { read(a1);read(b1); E[++tot].a[0] = a0;E[tot].b[0] = b0;E[tot].val = Inv2;MK[a0].pb(tot); E[++tot].a[0] = a1;E[tot].b[0] = b1;E[tot].val = Inv2;MK[a1].pb(tot); E[++tot].a[0] = a0;E[tot].b[0] = b0;E[tot].a[1] = a1;E[tot].b[1] = b1;E[tot].val = Inv4; MK[a0].pb(tot);MK[a1].pb(tot); if(t == 2) E[tot].val = MOD - Inv4; } }}void update(int &x,int y) { x += y; while(x >= MOD) x -= MOD;}void Solve() { fir[0] = 1; for(int i = 1 ; i < (1 << N) ; ++i) { fir[i] = min(fir[i >> 1] + 1,(i & 1) ? N + 1 : 1); } f[0][0] = 1; for(int S = 0 ; S < (1 << N) ; ++S) { for(auto k : f[S]) { int T = k.fi,val = k.se; //printf("%d %d %d\n",S,T,val); for(auto id : MK[fir[S]]) { if(T >> (E[id].b[0] - 1) & 1) continue; if(S >> (E[id].a[0] - 1) & 1) continue; if(E[id].a[1]) { if(E[id].a[0] == E[id].a[1] || E[id].b[0] == E[id].b[1]) continue; if(T >> (E[id].b[1] - 1) & 1) continue; if(S >> (E[id].a[1] - 1) & 1) continue; int a0 = E[id].a[0] - 1,a1 = E[id].a[1] - 1; int b0 = E[id].b[0] - 1,b1 = E[id].b[1] - 1; update(f[S | (1 << a0) | (1 << a1)][T | (1 << b0) | (1 << b1)],1LL * val * E[id].val % MOD); } else { int a0 = E[id].a[0] - 1,b0 = E[id].b[0] - 1; update(f[S | (1 << a0)][T | (1 << b0)],1LL * val * E[id].val % MOD); } } } } int ans = 1LL * fpow(2,N) * f[(1 << N) - 1][(1 << N) - 1] % MOD; out(ans);enter;}int main() {#ifdef ivorysi freopen("f1.in","r",stdin);#endif Init(); Solve(); return 0;}

转载于:https://www.cnblogs.com/ivorysi/p/9086285.html

你可能感兴趣的文章