F. Sports Betting 题解(状压dp+容斥)

题目链接

题目思路

数据范围很小，那么可以想到状压dp

设(dp[i])表示胜利者的集合为(i)的概率，(cal(i))为(i)的二进制数量

那么最后的答案为(largesum_{i=0}^{i=(1<<n)-1}dp[i]*cal(i))

重点在于如何计算(dp[i])

我们把(n)个元素分为两个集合，一个为(A)集合，一个为(B)集合

那么我们假设(B)集合中的所有边全部连向(A)集合

那么现在胜利者的集合是不是只能是(B)集合的所有子集的一种情况

假设(B)集合的所有边全部连向(A)集合的概率为(prob)

那么我们如何计算(dp[B])

一种比较显然的想法就是减去B中所有真子集得的答案 即对于任意(C)集合为(B)的真子集

(dp[B]=prob-sum dp[C])

但这样不是正确的，为什么？

我们观察图，我们必须还要B的所有边全部指向(C)的

设(rest=B igoplus C)

设(g)为(rest)中所有的边全部连向(A)的概率

最后的答案为(dp[B]=prob-sum dp[C] imes g)

时间复杂度为(O(3^nn^2))

代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=14+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-6;
int n;
int a[maxn];
int w[maxn][maxn];
bool vis[maxn];
int num[1<<14];
ll dp[1<<14];
ll qpow(ll a,ll b){
    ll ans=1,base=a;
    while(b){
        if(b&1) ans=ans*base%mod;
        base=base*base%mod;
        b=b>>1;
    }
    return ans;
}
int cal(int x){
    int cnt=0;
    while(x){
        if(x&1) cnt++;
        x=x/2;
    }
    return cnt;
}
signed main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            w[i][j]=a[i]*qpow(a[i]+a[j],mod-2)%mod;
        }
    }
    ll ans=0;
    for(int i=0;i<(1<<n);i++){
        for(int j=0;j<n;j++){
            if(i&(1<<j)) vis[j]=1;
            else vis[j]=0;
        }
        ll prob=1;
        for(int k=0;k<n;k++){
            if(!vis[k]) continue;
            for(int u=0;u<n;u++){
                if(vis[u]) continue;
                prob=prob*w[k][u]%mod;
            }
        }
        for(int j=i;j;j=(j-1)&i){
            ll g=1;
            int rest=(i^j);
            for(int k=0;k<n;k++){
                if(!(rest&(1<<k))) continue;
                for(int u=0;u<n;u++){
                    if(vis[u]) continue;
                    g=g*w[k][u]%mod;
                }
            }
            prob=((prob-g*dp[j])%mod+mod)%mod;
        }
        dp[i]=prob;
        ans=(ans+dp[i]*cal(i))%mod;
    }
    printf("%lld
",ans);
    return 0;
}