杭二集訓 disanti (51Nod 1667 機率好題)

标簽：組合數，數學，容斥原理

題目

題目傳送門

甲乙進行比賽。

他們各有k1,k2個集合[Li,Ri]

每次随機從他們擁有的每個集合中都取出一個數

S1=sigma甲取出的數，S2同理

若S1>S2甲勝 若S1=S2平局 否則乙勝

分别求出甲勝、平局、乙勝的機率。

（顯然這個機率是有理數，記為p/q，則輸出答案為（p/q）%(1e9+7)）（逆元）

注意 多組資料

Input

一個數，資料組數(T<=5)

對于每組資料 輸入順序為

k1 L1 R1…Lk1 Rk1

k2 L1 R1…Lk2 Rk2

(k1,k2<=8,1<=L<=R<=10^7)

Output

甲勝、平局、乙勝的機率。

（顯然這個機率是有理數，記為p/q，則輸出答案為（p/q）%(1e9+7)）（逆元）

Input示例

1

1 1 2

1 1 4

Output示例

125000001 250000002 625000005

分析

我們考慮

将小O的區間[L,R]拆成[-inf,L-1]和[-inf,R]

将小Y的區間[L,R]拆成[R+1,inf]和[L,inf]

(inf是一個相對較大的數)

再用容斥 考慮相對差

對于赢 用k1+k2+1個數(>=0)去填補相對差

對于平 用k1+k2個數(>=0)去填補相對差

每次計算貢獻用dfs即可

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define dep(i,a,b) for(ll i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
    ll f=,x=;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const ll p=e9+;
ll n,m,l,r,sum,len[],ans1,ans2,ans3,ni,T;
ll qpow(ll x,ll y){
    ll re=;
    while(y){
        if(y&)re=(re*x)%p;
        y>>=;
        x=x*x%p;
    }
    return re;
}
ll C(ll m,ll n){
    if(m<n)return ;
    ll ans=;
    rep(i,,n)ans=LL*ans*(m-n+i)%p;
    rep(i,,n)ans=LL*ans*qpow(i,p-)%p;
    return ans;
}
void dfs(int x,int y,int z){
    if(x>n+m){
        ans1=(ans1+y*C(sum-z+n+m-,n+m))%p;ans1=(ans1+p)%p;
        ans2=(ans2+y*C(sum-z+n+m-,n+m-))%p;ans2=(ans2+p)%p;
        return;
    }
    dfs(x+,y,z);dfs(x+,-y,z+len[x]);
}
int main()
{
    T=read();
    while(T--){
        sum=,ni=,ans1=ans2=ans3=;
        n=read();
        rep(i,,n){
            l=read(),r=read();
            sum+=r,len[i]=r-l+,ni=LL*ni*len[i]%p;
        }
        m=read();
        rep(i,,m){
            l=read(),r=read();
            sum-=l,len[i+n]=r-l+,ni=LL*ni*len[i+n]%p;
        }
        dfs(,,);ans3=(ni-ans1-ans2)%p;ans3=(ans3+p)%p;ni=qpow(ni,p-);
        ans1=LL*ans1*ni%p;ans2=LL*ans2*ni%p;ans3=LL*ans3*ni%p;
        printf("%lld %lld %lld\n",ans1,ans2,ans3);
    }
    return ;
}