题目链接

洛谷：https://www.luogu.org/problemnew/show/P4547

Solution

首先考虑只有第一类边的情况，那么每种完美匹配一定会由\(n\)个边组组成，概率就是\(1/2^n\)，对答案贡献为\(1\)，那么问题就转化成了统计完美匹配个数。

设\(f[s1][s2]\)表示当前左边情况为\(s1\)，右边为\(s2\)，在把其他的点填满可以得到的完美匹配的种类数，然后就是普及组\(dp\)，复杂度\(O(2^{2n})\)，但是这样会重复计数，而且复杂度不对。

如果我们把\(s1\)严格每次都从高位到低位转移，然后上记忆化搜索，复杂度可以降到\(O(2^n\cdot n^2)\)，且不会重复计数。

考虑其他两类边，我们硬点这些边都是单独的，概率\(50\%\)，但是这样会算不对，第二类边组在两条边都选的时候贡献的概率为\(25\%\)，但是应该是\(50\%\)，所以我们多加一个\(25\%\)的边组就好了，同理第三类边组添加一个概率为\(-25\%\)的边组，然后改一改上面的\(dp\)，记搜转移就好了，\(f\)开不下可以用\(\rm map\)。

#include<bits/stdc++.h>

using namespace std;

void read(int &x) {

    x=0;int f=1;char ch=getchar();

    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;

    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;

}

void print(int x) {

    if(x<0) putchar('-'),x=-x;

    if(!x) return ;print(x/10),putchar(x%10+48);

}

void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double

#define ll long long

#define pii pair<int,int >

#define vec vector<int >

#define pb push_back

#define mp make_pair

#define fr first

#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 1e4+10;

const int inf = 1e9;

const lf eps = 1e-8;

const int mod = 1e9+7;

const int inv2 = 5e8+4;

const int inv4 = 2.5e8+2;

int add(int x,int y) {return x+y>=mod?x+y-mod:x+y;}

int del(int x,int y) {return x-y<0?x-y+mod:x-y;}

int mul(int x,int y) {return 1ll*x*y-1ll*x*y/mod*mod;}

map<int,int > f;

int a[maxn],b[maxn],cnt,n,m;

int dfs(int s) {

    if(s==(1<<(n<<1))-1) return 1;

    if(f.find(s)!=f.end()) return f[s];int now=0,ans=0;

    for(int i=n-1;~i;i--) if(!(s&(1<<i))) {now=1<<i;break;}

    for(int i=1;i<=cnt;i++)

        if(!(a[i]&s)&&(now&a[i])) ans=add(ans,mul(b[i],dfs(s|a[i])));

    return f[s]=ans;

}

int main() {

    read(n),read(m);

    for(int i=1,s,s2,t,x,y;i<=m;i++) {

        read(t),read(x),read(y);x--,y--;

        s=1<<x|(1<<(y+n));a[++cnt]=s,b[cnt]=inv2;

        if(!t) continue;read(x),read(y);x--,y--;

        s2=1<<x|(1<<(y+n));a[++cnt]=s2,b[cnt]=inv2;

        if(s&s2) continue;

        a[++cnt]=s|s2,b[cnt]=t==1?inv4:mod-inv4;

    }write(mul(dfs(0),(int)pow(2,n)));

    return 0;

}

LOJ

[LOJ2290] [THUWC2017] 随机二分图

题目链接

Solution