51nod

分析

甲胜和乙胜类似，三者概率之和为 $1$，因此只考虑计算甲胜的概率，即甲胜的方案数除以总方案数。

设甲的第 $i$ 个数为 $X_i$，乙的第 $i$ 个数为 $Y_i$，则甲胜当且仅当
$$
\sum_{i=1}^{k_1}X_i>\sum_{i=1}^{k_2}Y_i
$$
设 $x_i=R1_i-X_i$，$y_i=Y_i-L2_i$，上式化为
$$
\sum_{i=1}^{k_1}R1_i-\sum_{i=1}^{k_1}x_i>\sum_{i=1}^{k_2}y_i-\sum_{i=1}^{k_2}L2_i
$$
移项得到
$$
\sum_{i=1}^{k_1}x_i+\sum_{i=1}^{k_2}y_i<\sum_{i=1}^{k_1}R1_i+\sum_{i=1}^{k_2}L2_i
$$
添加一个辅助变量 $k$，将其转化为等式得到
$$
\sum_{i=1}^{k_1}x_i+\sum_{i=1}^{k_2}y_i+k=\sum_{i=1}^{k_1}R1_i+\sum_{i=1}^{k_2}L2_i-1
$$
则我们相当于要求这个 $k_1+k_2+1$ 元不定方程的非负解数，其中一些变量有上界。

考虑容斥掉上界的限制，即钦定一些变量超过了上界，则我们只需要计算不定方程 $\sum_{i=1}^n x_i=X$ 的非负解数，相当于在 $X$ 个物品间插 $n-1$ 个板且允许多个板插在两个物品间，则解数为 ${X+n-1\choose n-1}$。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
#define popcount __builtin_popcount
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=10;

int k1,k2,L1[N],R1[N],L2[N],R2[N],sum;

const int mod=1e9+7;
inline int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

inline int C(ll n,int m) {
    if (n<m) return 0;
    int res=1;
    for (re ll i=n-m+1;i<=n;++i) res=i%mod*res%mod;
    for (re int i=1;i<=m;++i) res=1ll*res*qpow(i,mod-2)%mod;
    return res;
}

inline int calc(int op) {
    ll s=-1;
    if (op==1) {
        for (re int i=1;i<=k1;++i) s+=R1[i];
        for (re int i=1;i<=k2;++i) s-=L2[i];
    } else {
        for (re int i=1;i<=k2;++i) s+=R2[i];
        for (re int i=1;i<=k1;++i) s-=L1[i];
    }
    int ans=0;
    for (re int S=0;S<1<<(k1+k2);++S) {
        ll ss=s;
        for (re int i=1;i<=k1;++i)
            if (S&(1<<(i-1))) ss-=R1[i]-L1[i]+1;
        for (re int i=1;i<=k2;++i)
            if (S&(1<<(i+k1-1))) ss-=R2[i]-L2[i]+1;
        if (popcount(S)&1) ans=(ans-C(ss+k1+k2,k1+k2)+mod)%mod;
        else ans=(ans+C(ss+k1+k2,k1+k2))%mod;
    }
    return 1ll*ans*qpow(sum,mod-2)%mod;
}

int main() {
    int T=read();
    while (T--) {
        k1=read();
        for (re int i=1;i<=k1;++i) L1[i]=read(),R1[i]=read();
        k2=read();
        for (re int i=1;i<=k2;++i) L2[i]=read(),R2[i]=read();
        sum=1;
        for (re int i=1;i<=k1;++i) sum=1ll*sum*(R1[i]-L1[i]+1)%mod;
        for (re int i=1;i<=k2;++i) sum=1ll*sum*(R2[i]-L2[i]+1)%mod;
        int ans1=calc(1),ans3=calc(3),ans2=((1-ans1-ans3)%mod+mod)%mod;
        printf("%d %d %d\n",ans1,ans2,ans3);
    }
    return 0;
}