Description
Solution
假设甲在第 (i) 个区间选的是 (R_i-x_i) ，乙在第 (i) 个区间选的是 (L_i+y_i) 。若甲胜利则有
[sum_{i=1}^{k_1}R_i-x_i>sum_{i=1}^{k_2}L_i+y_i
]
其中
[0le x_ile R_i-L_i,0le y_ile R_i-L_i
]
移一下项
[sum_{i=1}^{k_1}x_i+sum_{i=1}^{k_2}y_i<sum_{i=1}^{k_1}R_i-sum_{i=1}^{k_2}L_i
]
令
[m=sum_{i=1}^{k_1}R_i-sum_{i=1}^{k_2}L_i
]
则有
[sum_{i=1}^{k_1}x_i+sum_{i=1}^{k_2}y_ile m - 1
]
定义新变量 (kin[0,+infty]) 则有
[sum_{i=1}^{k_1}x_i+sum_{i=1}^{k_2}y_i+k= m - 1
]
于是就有了 (k_1+k_2+1) 个变量。简单容斥一下就好了。平局的情况把 (k) 上届置为 (0) ，等式右边改成 (m) 就行了。
#include<bits/stdc++.h>
using namespace std;
template <class T> void read(T &x) {
x = 0; bool flag = 0; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == 45) flag = 1;
for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48; if (flag) x = -x;
}
#define N 30
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define P 1000000007
#define INF 0x3f3f3f3f
#define ll long long
int k1, k2, m, up[N];
ll ans;
ll qpow(ll x, int k = P - 2) {
ll ret = 1;
for (; k; k >>= 1, (x *= x) %= P) if (k & 1) (ret *= x) %= P;
return ret;
}
ll C(int n, int m) {
if (n < m) return 0;
ll ret = 1;
rep(i, n - m + 1, n) (ret *= i) %= P;
rep(i, 1, m) (ret *= qpow(i)) %= P;
return ret;
}
void dfs(int x, bool cur, int m) {
if (m < 0) return;
if (x == k1 + k2 + 1) {
int t = (up[x] == 0);
if (cur) ans = (ans + P - C(m + k1 + k2 - t, k1 + k2 - t)) % P;
else (ans += C(m + k1 + k2 - t, k1 + k2 - t)) %= P;
return;
}
dfs(x + 1, 1 - cur, m - up[x] - 1), dfs(x + 1, cur, m);
}
void calcInv() {
rep(i, 1, k1 + k2) (ans *= qpow(up[i] + 1)) %= P;
}
int main() {
int T; read(T);
while (T--) {
m = 0;
read(k1);
rep(i, 1, k1) {
int l, r; read(l), read(r);
up[i] = r - l, m += r;
}
read(k2);
rep(i, 1, k2) {
int l, r; read(l), read(r);
up[i + k1] = r - l, m -= l;
}
up[k1 + k2 + 1] = INF, m--, ans = 0;
dfs(1, 0, m), calcInv();
ll t = ans; ans = 0;
up[k1 + k2 + 1] = 0, m++;
dfs(1, 0, m), calcInv();
printf("%lld %lld %lld
", t, ans, (1 + P + P - t - ans) % P);
}
return 0;
}