Problem 甲乙进行比赛。
他们各有 k1,k2 个集合 [Li,Ri]
每次随机从他们拥有的每个集合中都取出一个数
S1=∑ 甲取出的数
S2 同理
若 S1>S2 甲胜 若 S1=S2 平局 否则乙胜
分别求出甲胜、平局、乙胜的概率。
Solution 对于甲的每个数可以表示为这样一个形式 Ri?xi 其中 xi∈[0,Ri?Li]
类似的，对于乙中的每个数可以表示为这样一个形式 Li+yi 其中 yi∈[0,Ri?Li]
那么甲胜利的条件即为：
∑Ri?∑xi>∑Li+∑yi
变形为：
∑xi+∑yi<∑Ri?∑Li
于是可以发现右边的是一个常数
我们加入一个变量 k(k∈[0,+∞)
那么不等式变成：
∑xi+∑yi+k=∑Ri?∑Li?1
(注意有一个-1是因为不等式中是<)
于是就变成了求方程有多少个不同的解。
容斥 问题现在变成：
我们有一个有 k1+k2+1 个未知数的方程，其中每个未知数都是非负整数且有上限，现在我们需要知道有多少组解。
于是我们可以容斥，答案要求的是满足所有未知数都在其上限以内的方案数，于是设 S(i) 表示至少有i个未知数不符合要求的方案数，那么可以得到：
Ans=∑(?1)i×S(i)
枚举未知数符合或不符合的状态，那么对于一个不符合要求的未知数，由于原本应当是 xi≤upi ，不符合就变成 xi>upi ，即 xi?upi?1≥0
所以将等式的常数减去 upi+1 就变成了经典的挡板问题：将n个球放进m个盒子里，求方案数。（注意：由于此问题中m很小，于是可以直接暴力算组合数）
记第一道640 【解题报告|51nod 1667 概率好题】
文章图片
Code
#include
#include
#include
#include
#include#define fo(i,a,b) for(int i=a;
i<=b;
i++)
#define fd(i,a,b) for(int i=a;
i>=b;
i--)using namespace std;
int get(){
char ch;
int s=0;
bool bz=0;
while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
if (ch=='-')bz=1;
else s=ch-'0';
while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
if (bz)return -s;
return s;
}const int N = 20;
const int mo = 1e+9+7;
typedef long long LL;
int u[N];
int n,k1,k2,t;
LL sum,ans;
bool bz[N];
LL quickmi(LL x,LL tim){
LL ans=1;
while(tim){
if (tim%2)ans=ans*x%mo;
x=x*x%mo;
tim/=2;
}
return ans;
}LL c(LL n,int m){
LL ans=1;
fo(i,1,m)ans=ans*(n-i+1)%mo;
fo(i,1,m)ans=ans*quickmi(i,mo-2)%mo;
return ans;
}void calc(){
LL tmp=sum;
fo(i,1,n)
if (bz[i])tmp-=u[i]+1;
if (tmp<0)return;
LL v=c(tmp+n,n);
bool pd=0;
fo(i,1,n)pd^=bz[i];
if (pd)ans=(ans+mo-v)%mo;
else ans=(ans+v)%mo;
}void getans(int x){
if (x>n){
calc();
return;
}
bz[x]=0;
getans(x+1);
bz[x]=1;
getans(x+1);
}int main(){
t=get();
fo(cas,1,t){
k1=get();
sum=0;
fo(i,1,k1){
int l=get(),r=get();
u[i]=r-l;
sum+=r;
}
k2=get();
fo(i,1,k2){
int l=get(),r=get();
u[i+k1]=r-l;
sum-=l;
}
n=k1+k2;
u[n+1]=1e+9;
sum--;
LL ans1=0;
ans=0;
if(sum<0)ans1=0;
else{
getans(1);
ans1=ans;
}
ans=0;
sum++;
if (sum<0)ans=0;
else getans(1);
ans=(ans-ans1+mo)%mo;
fo(i,1,n)ans=ans*quickmi(u[i]+1,mo-2)%mo;
fo(i,1,n)ans1=ans1*quickmi(u[i]+1,mo-2)%mo;
printf("%lld %lld %lld\n",ans1,ans,(1+mo*2-ans-ans1)%mo);
}
return 0;
} 推荐阅读
- HDU 5519 Kykneion asma（沈阳站K题&&DP+容斥）
- 树形dp|Codeforces 917D Stranger Trees 树形dp+容斥原理
- ACM|Jzzhu and Sequences(CF #257 Div. 2)
- DP|[codeforces 917D]Stranger Trees
- 容斥原理|【WC2017模拟1.22】简单题
- codeforces|codeforces #531(div3)解题报告 Apare_xzc
- 容斥原理（翻译）
- 解题报告|【算法学习笔记】23.动态规划 解题报告 SJTU_OJ 1280 整装待发