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

## 容斥原理之妙

Posted by yjjr's blog on January 6, 2018

# 题目

Output

Input示例

1 1 1 2 1 1 4

Output示例

125000001 250000002 625000005

# 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;
}