51Nod1667 概率好题 <容斥+计数>

Problem

概率好题

$\mathrm{Time\;Limit:\;4\;Sec}$
$\mathrm{Memory\;Limit:\;131072\;KB}$

Description

甲乙进行比赛，他们各有$k_1,k_2$个集合$[L_i,R_i]$，每次随机从他们拥有的每个集合中都取出一个数。
$S_1=\sum甲取出的数$，$S_2$同理。若$S_1>S_2$甲胜；若$S_1=S_2$平局；否则乙胜。
分别求出甲胜、平局、乙胜的概率。
（显然这个概率是有理数，记为$\frac{p}{q}$，则输出答案为$\frac{p}{q}\bmod{10^9+7}$（逆元）
注意：多组数据

Input

一个数，数据组数$(T\le5)$
对于每组数据 输入顺序为

k1 L1 R1 ... Lk1 Rk1
k2 L1 R1 ... Lk2 Rk2

$(k_1,k_2\le8,1\le L\le R\le10^7)$

Output

甲胜、平局、乙胜的概率。

Input示例

1
1 1 2
1 1 4

Output示例

125000001 250000002 625000005

标签：容斥 计数DP

Solution

设甲取的数为$R_{1,1}-x_1,R_{1,2}-x_2,\cdots,R_{1,k_1}-x_{k_1}$，乙取的数为$L_{2,1}+y_1,L_{2,2}+y_2,\cdots,L_{2,k_2}+y_{k_2}$。显然有$x_i\in[0,R_{1,i}-L_{1,i}]$，$y_i\in[0,R_{2,i}-L_{2,i}]$。

以甲胜为例，有

$$\sum_{i=1}^{k_1}R_{1,i}-\sum_{i=1}^{k_1}x_i>\sum_{i=1}^{k_2}y_i+\sum_{i=1}^{k_2}L_{2,i}$$

移项得

$$\sum_{i=1}^{k_1}x_i+\sum_{i=1}^{k_2}y_i<C$$

其中$C=\sum_{i=1}^{k_1}R_{1,i}-\sum_{i=1}^{k_2}L_{2,i}$。
加入变量$t\in[0,\infty]$，使得有

$$\sum_{i=1}^{k_1}x_i+\sum_{i=1}^{k_2}y_i+k=C-1$$

答案变成这个方程解的个数。

由于前$k_1+k_2$个变量都有上限制约，我们可以容斥一下，求有至少$p$个变量超过上限时的解的个数。
这$p$个变量一定呈$lim+x'$的形式，其中$lim$为上限，$x'\in[0,\infty]$。
这样的解的个数就是将$C-1-\sum lim$拆为$k_1+k_2+1$个数的方案数，显然由隔板法这个值为

$$\binom{C-1-\sum lim+k_1+k_2}{k_1+k_2}$$

设这样求出的至少$p$个变量超过上限时的解的个数为$S_p$，那么甲胜的情况数为

$$ans=\sum_{i=0}^{n}(-1)^iS_i$$

同理可以求出平局的情况，求出两者的概率，用$1$减去即可得到乙胜的概率。

Code

#include <bits/stdc++.h>
#define P 1000000007
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, n1, n2, r[20];
lnt s, sa, sb, sc; bool mrk[20];
lnt inv(lnt x) {
    lnt ret = 1;
    for (int k = P-2; k; k >>= 1, x = x*x%P)
        if (k&1) ret = ret*x%P;
    return ret;
}
lnt C(lnt n, int m) {
    lnt ret = 1;
    for (int i = 1; i <= m; i++) ret = ret*(n-i+1)%P;
    for (int i = 1; i <= m; i++) ret = ret*inv(i)%P;
    return ret;
}
void upd(lnt &res) {
    lnt ss = s, f = 1;
    for (int i = 1; i <= n; i++)
        if (mrk[i]) ss -= (r[i]+1), f *= -1;
    if (ss >= 0) res = (res+f*C(ss+n, n)+P)%P;
}
void DFS(int stp, lnt &res) {
    if (s < 0) {res = 0; return;}
    if (stp > n) {upd(res); return;}
    mrk[stp] = true, DFS(stp+1, res);
    mrk[stp] = false, DFS(stp+1, res);
}
int main() {
    int T; read(T);
    while (T--) {
        read(n1), s = sa = sb = sc = 0;
        for (int i = 1, L, R; i <= n1; i++)
            read(L), read(R), r[i] = R-L, s += R;
        read(n2);
        for (int i = 1, L, R; i <= n2; i++)
            read(L), read(R), r[i+n1] = R-L, s -= L;
        n = n1+n2, r[n+1] = 0x7f7f7f7f;
        s--, DFS(1, sa), s++, DFS(1, sc), sc = (sc-sa+P)%P;
        for (int i = 1; i <= n; i++) sa = sa*inv(r[i]+1)%P;
        for (int i = 1; i <= n; i++) sc = sc*inv(r[i]+1)%P;
        sb = (1-sa-sc+P+P)%P, printf("%lld %lld %lld\n", sa, sc, sb);
    }
    return 0;
}