51nod1667 概率好题(容斥)

51nod1667 概率好题(容斥)

题目大意

甲乙进行比赛。他们各有k1,k2个集合[Li,Ri]

每次随机从他们拥有的每个集合中都取出一个数

S1=sigma甲取出的数，S2同理

若S1>S2甲胜 若S1=S2平局 否则乙胜

分别求出甲胜、平局、乙胜的概率。(mod 1e9+7)

数据范围

(k1,k2<=8,1<=L<=R<=10^7)

解题思路

好题确实

[sum_{i=1}^{k1}A_i(L_ile A_i le R_i) < sum_{i=1}^{k2}B_i(L_i le B_i le R_i)\ sum_{i=1}^{k1}x_i + L_i < sum_{i=1}^{k2}R_i- x_i\ sum_{i=1}^{k1}x_i + sum_{i=1}^{k2}x_i < sum_{i=1}^{k2}R_i - sum_{i=1}^{k1} L_i\ ]

这是经典的整数解方程，隔板法即可

考虑到 x 有不同的上限，那么容斥即可

const int N = 25;
const int P = 1e9+7;
int l1[N], l2[N], r1[N], r2[N], L[N], T, k1, k2;

ll fpw(ll x, ll mi) {
	ll res = 1;
	for (; mi; mi >>= 1, x = x * x % P)
		if (mi & 1) res = res * x % P;
	return res;
}

ll C(ll n, ll m) {
	ll up = 1, dw = 1;
	for (int i = n;i >= n - m + 1; i--)
		up = up * i % P;
	for (int i = 1;i <= m; i++)
		dw = dw * i % P;
	return up * fpw(dw, P - 2) % P;
}

ll work(int k1, int k2) {
	ll lim = 0, ans = 0;
	for (int i = 1;i <= k2; i++) lim += r2[i];
	for (int i = 1;i <= k1; i++) lim -= l1[i];
	int all = (1 << (k1 + k2)) - 1;
	for (int i = 1;i <= k1; i++) 
		L[i] = r1[i] - l1[i] + 1;
	for (int i = 1;i <= k2; i++) 
		L[i + k1] = r2[i] - l2[i] + 1;
	for (int i = 0;i <= all; i++) {
		ll res = lim, siz = 0;
		for (int j = 1;j <= k1 + k2; j++) 
			if (i & (1 << (j - 1))) res -= L[j], siz++;
		if (res <= 0) continue;
		if (siz & 1) ans -= C(res + k1 + k2 - 1, k1 + k2);
		else ans += C(res + k1 + k2 - 1, k1 + k2);
		ans %= P;
	}
	return (ans % P + P) % P;
}

int main() {
	for (read(T); T; T--) {
		read(k1); ll res = 1;
		for (int i = 1;i <= k1; i++) 
			read(l1[i]), read(r1[i]), res = res * (r1[i] - l1[i] + 1) % P;
		read(k2);
		for (int i = 1;i <= k2; i++)
			read(l2[i]), read(r2[i]), res = res * (r2[i] - l2[i] + 1) % P;;
		res = fpw(res, P - 2);
		ll p1 = work(k1, k2) * res % P;
		swap(l1, l2), swap(r1, r2);
		ll p3 = work(k2, k1) * res % P;
		ll p2 = (1 - p1 - p3 + P + P) % P;
		printf ("%lld %lld %lld
", p3, p2, p1);
	}
	return 0;
}