题解 P4547 【[THUWC2017]随机二分图】

这里会证明为什么这个诡异的算法是对的 _______________ 题意比较清楚了这里就不在赘述 我也不知道那个乘$2^n$的条件有什么用，所以我是直接算出期望来然后乘的 我们发现一个非常重要的事实是，假设我们求出了这张图的一个完美匹配的边集，那么我们随便向这个边集里怼一些边也是不会改变这张图依然有完美匹配的性质的。 因此我们需要做的就是枚举所有可能的匹配方案然后把这些方案的概率加到一起就是我们需要的答案 那么我们怎么枚举呢？我们先来考虑所有的边都是第0类边组的情况 我们令$dp(S)$表示S这个集合实现完美匹配的期望数量，那么容易发现S的siz一定是个偶数，所以总的状态量是${30 \choose 15}$级别的 那么我们现在转移的时候为了不重不漏的枚举每一种方案，我们有必要给这个方案中的边排一个序，否则同一种边集将会以不同的顺序被计数好几次 那么我们就简单粗暴的按照左部点编号排序就行了 因此dp(S)转移的时候应该是枚举S的lowbit的所有出边，然后删掉这条出边进行转移，这样可以保证dp出来的所有方案中的边都是按照左部点编号排好序的，当然无论如何我们选择的边都只有0.5概率出现，所以答案要乘一个0.5 如此这般dp我们就可以解决所有边都是第0类边的情况了 那么问题来了我们还有边组的问题 先来考虑第一类边组，如果我们强行认为这两个边都是独立的话，第一条边单独出现在**匹配方案**中的概率是50%,第二条边单独出现在**匹配方案**中的概率是50%，两条边同时出现在**匹配方案**中的概率是25% 而真实情况是第一条边,第一条边单独出现在匹配方案中的概率是50%,同时出现在匹配方案的概率也是50%，出现这种情况是因为我们只关心出现在匹配方案中的边是否出现而不关心这张图里到底出现什么边 那么看起来情况比我们想像的简单，如果这两个边的左部点相同那么我们直接认为两条边相互之间独立，否则我们把左部点较大的边挂在左部点较小的边上，如果选择了那个左部点较小的边我们有25%的概率立即选择另一条边(前提是你能同时删掉这4个点)，这样的话我们概率就对上了 同时我们的方案现在也是排好序的，你可以认为一个边组的关键字是最小的左部点编号 同样的第2类边组其实就是两条边不可能同时出现，所以我们在选择第一条边的时候有-25%的概率选择第二条边即可 然后剩下的大力状压记忆化就行了 上代码~ ```C // luogu-judger-enable-o2 #include<cstdio> #include<algorithm> #include<tr1/unordered_map> using namespace std::tr1; using namespace std;typedef unsigned long long ll;const int N=20; const ll mod=1e9+7;const ll qu=250000002;const ll mqu=750000005;const ll ha=500000004; inline ll po(ll a,ll p){ll r=1;for(;p;p>>=1,a=a*a%mod)if(p&1)r=r*a%mod;return r;} unordered_map <int,ll> dp;int mp[N];int tw[N][N];ll val[N][N];int n;int m; inline ll dfs(int s)//记忆化 { if(s==0)return 1;if(dp.count(s))return dp[s];int mi=0;ll dv=0; for(int i=0;i<n;i++){if((s>>i)&1){mi=i;break;}}int p=(s>>15)&mp[mi];int del=s^(1<<mi); for(int i=0,k;i<n;i++) if((p>>i)&1) { k=del^(1<<(15+i));(dv+=ha*dfs(k))%=mod;int ne=tw[mi][i]; if(ne&&((ne&k)==ne))(dv+=val[mi][i]*dfs(k^ne))%=mod; } return dp[s]=dv; } int main() { scanf("%d%d",&n,&m); for(int i=1,t,u1,v1,u2,v2;i<=m;i++) { scanf("%d%d%d",&t,&u1,&v1);u1--;v1--; switch(t) { case 0:{mp[u1]|=(1<<v1);break;} case 1: { scanf("%d%d",&u2,&v2);u2--;v2--; if(u1>u2)swap(u1,u2),swap(v1,v2);mp[u1]|=(1<<v1);mp[u2]|=(1<<v2); tw[u1][v1]=(1<<u2)|(1<<(v2+15));val[u1][v1]=qu;break; } case 2: { scanf("%d%d",&u2,&v2);u2--;v2--; if(u1>u2)swap(u1,u2),swap(v1,v2);mp[u1]|=(1<<v1);mp[u2]|=(1<<v2); tw[u1][v1]=(1<<u2)|(1<<(v2+15));val[u1][v1]=mqu;break; } } }int s=(1<<n)-1;printf("%llu",dfs((s<<15)|s)*po(2,n)%mod);return 0; } ```