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

Problem

概率好题

Description

甲乙进行比赛，他们各有个集合，每次随机从他们拥有的每个集合中都取出一个数。
，同理。若甲胜；若平局；否则乙胜。
分别求出甲胜、平局、乙胜的概率。
（显然这个概率是有理数，记为，则输出答案为（逆元）
注意：多组数据

Input

一个数，数据组数
对于每组数据输入顺序为

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

Output

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

Input示例

1
2
3

1
1 1 2
1 1 4

Output示例

1	125000001 250000002 625000005

标签：容斥 计数DP

Solution

设甲取的数为，乙取的数为。显然有，。

以甲胜为例，有

移项得

其中。
加入变量，使得有

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

由于前个变量都有上限制约，我们可以容斥一下，求有至少个变量超过上限时的解的个数。
这个变量一定呈的形式，其中为上限，。
这样的解的个数就是将拆为个数的方案数，显然由隔板法这个值为

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

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

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