标签：组合数，数学，容斥原理
题目
甲乙进行比赛。 他们各有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=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const ll p=1e9+7;
ll n,m,l,r,sum,len[26],ans1,ans2,ans3,ni,T;
ll qpow(ll x,ll y){
ll re=1;
while(y){
if(y&1)re=(re*x)%p;
y>>=1;
x=x*x%p;
}
return re;
}
ll C(ll m,ll n){
if(m<n)return 0;
ll ans=1;
rep(i,1,n)ans=1LL*ans*(m-n+i)%p;
rep(i,1,n)ans=1LL*ans*qpow(i,p-2)%p;
return ans;
}
void dfs(int x,int y,int z){
if(x>n+m){
ans1=(ans1+y*C(sum-z+n+m-1,n+m))%p;ans1=(ans1+p)%p;
ans2=(ans2+y*C(sum-z+n+m-1,n+m-1))%p;ans2=(ans2+p)%p;
return;
}
dfs(x+1,y,z);dfs(x+1,-y,z+len[x]);
}
int main()
{
T=read();
while(T--){
sum=0,ni=1,ans1=ans2=ans3=0;
n=read();
rep(i,1,n){
l=read(),r=read();
sum+=r,len[i]=r-l+1,ni=1LL*ni*len[i]%p;
}
m=read();
rep(i,1,m){
l=read(),r=read();
sum-=l,len[i+n]=r-l+1,ni=1LL*ni*len[i+n]%p;
}
dfs(1,1,0);ans3=(ni-ans1-ans2)%p;ans3=(ans3+p)%p;ni=qpow(ni,p-2);
ans1=1LL*ans1*ni%p;ans2=1LL*ans2*ni%p;ans3=1LL*ans3*ni%p;
printf("%lld %lld %lld\n",ans1,ans2,ans3);
}
return 0;
}
