杭二集训 disanti(51Nod 1667 概率好题)

容斥原理之妙

Posted by yjjr's blog on January 6, 2018

标签:组合数,数学,容斥原理

题目

题目传送门

甲乙进行比赛。 他们各有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;
}

本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr