评测平台
Description
Given l 1 , r 1 , l 2 , r 2 , l 3 , r 3 , l 4 , r 4 l1,r1,l2,r2,l3,r3,l4,r4 l1,r1,l2,r2,l3,r3,l4,r4, please count the number of four-tuples ( x 1 , x 2 , x 3 , x 4 ) (x1,x2,x3,x4) (x1,x2,x3,x4) such that l i ≤ x i ≤ r i li≤xi≤ri li≤xi≤ri and x 1 ≠ x 2 , x 2 ≠ x 3 , x 3 ≠ x 4 , x 4 ≠ x 1 x1≠x2,x2≠x3,x3≠x4,x4≠x1 x1=x2,x2=x3,x3=x4,x4=x1. The answer should modulo 1 0 9 + 7 10^9+7 109+7 before output.
Input
The input consists of several test cases. The first line gives the number of test cases, T ( 1 ≤ T ≤ 1 0 6 ) T(1≤T≤10^6) T(1≤T≤106). For each test case, the input contains one line with 8 integers l 1 , r 1 , l 2 , r 2 , l 3 , r 3 , l 4 , r 4 ( 1 ≤ l i ≤ r i ≤ 1 0 9 ) l1,r1,l2,r2,l3,r3,l4,r4(1≤li≤ri≤10^9) l1,r1,l2,r2,l3,r3,l4,r4(1≤li≤ri≤109)
Output
For each test case, output one line containing one integer, representing the answer.
Samples Input Copy
1 1 1 2 2 3 3 4 4
Output
1
题目大意：分别给出四个区间的左右端点，然后在这四个区间中依次选择一个整数，分别用 x 1 , x 2 , x 3 , x 4 x1,x2,x3,x4 x1,x2,x3,x4 来表示，求使得所选数字满足 x 1 ≠ x 2 , x 2 ≠ x 3 , x 3 ≠ x 4 , x 4 ≠ x 1 x1≠x2,x2≠x3,x3≠x4,x4≠x1 x1=x2,x2=x3,x3=x4,x4=x1情况的共有多少组。
解题思路：利用集合容斥原理来解决，首先很容易就可以计算出全集，对于不满足上述条件的集合也可以枚举求出来，答案就是全集减去不满足条件的所有集合。下面给出图片来展现推导过程： 附上代码：
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int mod = 1e9+7; int main() { int T; scanf("%d",&T); while(T--) { ll l1,r1,l2,r2,l3,r3,l4,r4; scanf("%lld%lld%lld%lld%lld%lld%lld%lld",&l1,&r1,&l2,&r2,&l3,&r3,&l4,&r4); ll len1 = r1 - l1 + 1; ll len2 = r2 - l2 + 1; ll len3 = r3 - l3 + 1; ll len4 = r4 - l4 + 1; ll ans = (len1 % mod) * (len2 % mod) % mod;//全集 ans = (ans % mod) * (len3 % mod) % mod; ans = (ans % mod) * (len4 % mod) % mod; ll sum1 = 0,sum2 = 0,sum3 = 0;//记录四种情况的个数 //x1==x2 ll l = max(l1,l2),r = min(r1,r2); if(r >= l) { sum1 += ((((r - l + 1) % mod) * (len3 % mod) % mod) % mod) * (len4 % mod) % mod; } //x1==x4 l = max(l1,l4),r = min(r1,r4); if(r >= l) { sum1 += ((((r - l + 1) % mod) * (len2 % mod) % mod) % mod) * (len3 % mod) % mod; } //x2==x3 l = max(l2,l3),r = min(r2,r3); if(r >= l) { sum1 += ((((r - l + 1) % mod) * (len1 % mod) % mod) % mod) * (len4 % mod) % mod; } //x3==x4 l = max(l3,l4),r = min(r3,r4); if(r >= l) { sum1 += ((((r - l + 1) % mod) * (len1 % mod) % mod) % mod) * (len2 % mod) % mod; } //x1==x2==x4 l = max(l1,max(l2,l4)),r=min(r1,min(r2,r4)); if(r >= l) { sum2 += ((r - l + 1) % mod) * (len3 % mod) % mod; } //x1==x2==x3 l = max(l1,max(l2,l3)),r=min(r1,min(r2,r3)); if(r >= l) { sum2 += ((r - l + 1) % mod) * (len4 % mod) % mod; } //x1==x3==x4 l = max(l1,max(l3,l4)),r=min(r1,min(r3,r4)); if(r >= l) { sum2 += ((r - l + 1) % mod) * (len2 % mod) % mod; } //x2==x3==x4 l = max(l2,max(l3,l4)),r=min(r2,min(r3,r4)); if(r >= l) { sum2 += ((r - l + 1) % mod) * (len1 % mod) % mod; } //x1==x2&&x3==x4 ll L1 = max(l1,l2),R1 = min(r1,r2),L2 = max(l3,l4),R2 = min(r3,r4); if(R1 >= L1 && R2 >= L2) { sum2 += ((R1 - L1 + 1) % mod) * ((R2 - L2 + 1) % mod) % mod; } //x1==x4&&x2==x3 L1 = max(l1,l4),R1 = min(r1,r4),L2 = max(l2,l3),R2 = min(r2,r3); if(R1 >= L1 && R2 >= L2) { sum2 += ((R1 - L1 + 1) % mod) * ((R2 - L2 + 1) % mod) % mod; } //x1==x2==x3==x4 l = max(l1,max(l2,max(l3,l4))),r = min(r1,min(r2,min(r3,r4))); if(r >= l) { sum3 += r - l + 1; } ans -= sum1; ans = ((ans % mod) + mod) % mod; ans += sum2; ans %= mod; ans -= 3 * sum3; ans = ((ans % mod) + mod) % mod; printf("%lld\n",ans); } return 0; } /* 1 1 1000000000 1 1000000000 1 1000000000 1 1000000000 */注意：取余的时候需要特别注意一下，稍有不慎就很容易溢出。 再者就是当考虑，（ x 1 x1 x1== x 2 x2 x2 && x 3 x3 x3== x 4 x4 x4）和（ x 1 x1 x1== x 3 x3 x3 && x 2 x2 x2== x 4 x4 x4）的时候。拿出其中一个来进行解释，如果&&的左右两边都有交集存在的话，只需计算两个交集中元素的数量相乘即可，如果有一方不存在交集，此种情况的结果直接为 0 0 0 就行。
