[THUWC2017]随机二分图

LOJ 2290

思路

我们可以发现,如果只有第一类边,这个题是很好做的,直接大力记搜就可以了,为了不重不漏,需要按顺序进行转移,至于是排个序转移还是每次转移最高位都可以。

那么想办法把第二类和第三类边转化成第一类边。将第二类边的两条边分别称为$e_1$和$e_2$,那么只有$e_1$或只有$e_2$作出贡献的概率是$50\%$,这样计算的话还会包含$25\%$的同时作出贡献的概率,因为按题目的本意需要有$50\%$的同时作出贡献的概率,所以就再加一个$e_1, e_2$同时出现,概率$25\%$的情况。第三类边同理,拆开后就是$e_1\to 50\%$,$e_2\to 50\%$,$e_1, e_2\to 25\%$

代码

#include <iostream>
#include <cstdio>
#include <map>
#include <vector>

template <typename T> void in(T &_){
    char c=getchar(); while(c<'0'||c>'9') c=getchar();
    _=0; while(c>='0'&&c<='9') _=_*10+c-'0', c=getchar();
}
template <typename T, typename ...A> void in(T &_, A &...a){in(_); in(a...);}

const int MOD=1e9+7, inv2=500000004, inv4=250000002;
std::map<int, int>mp;
std::vector<std::pair<int, int> >vec;
int N, M;
int dfs(int sta){
    if(mp.find(sta)!=mp.end()) return mp[sta];
    int ans=0;
    for(auto i: vec){
        int now=i.first;
        if((now&sta)==now && sta<(now<<1)) ans=(ans+1LL*dfs(now^sta)*i.second%MOD)%MOD;
    }
    return mp[sta]=ans;
}

int main(){
    int opt, a1, b1, a2, b2;
    mp[0]=1;
    in(N, M);
    for(int i=1; i<=M; i++){
        in(opt, a1, b1);
        int sta=(1<<(a1-1))|(1<<(b1+N-1));
        vec.push_back(std::make_pair(sta, inv2));
        if(opt){
            in(a2, b2);
            sta=(1<<(a2-1))|(1<<(b2+N-1));
            vec.push_back(std::make_pair(sta, inv2));
            if(((1<<(a1-1))|(1<<(b1+N-1)))&sta) continue;
            sta|=(1<<(a1-1))|(1<<(b1+N-1));
            vec.push_back(std::make_pair(sta, (opt==1?inv4:MOD-inv4)));
        }
    }
    printf("%lld\n", (1LL<<N)*dfs((1<<(2*N))-1)%MOD);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注