Problem F.Four-tuples
Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 143 Accepted Submission(s): 36
Problem Description
Given l1,r1,l2,r2,l3,r3,l4,r4, please count the number of four-tuples (x1,x2,x3,x4) such that li≤xi≤ri and x1≠x2,x2≠x3,x3≠x4,x4≠x1. The answer should modulo 109+7 before output.
Input
The input consists of several test cases. The first line gives the number of test cases, T(1≤T≤106).
For each test case, the input contains one line with 8 integers 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.
Sample Input
1
1 1 2 2 3 3 4 4
Sample Output
1
题目大意：给你四个区间，要求每个区间选一个数组成一个四元组（x1,x2,x3,x4）要求：
x1≠x2，x2≠x3，x3≠x4，x4≠x1
li<=xi<=ri
解题思路：（容斥原理）
先将四个区间长度的乘积作为答案。
分别减去 x1=x2，x2=x3，x3=x4，x4=x1 四种情况的组合数量（每种情况中未提及的变量在其区间中任选，即统计答案时直接乘区间长度） 。
因为减去 x1=x2 和 x2=x3 时会重复减去 x1=x2=x3 的情况，所以要加回来，类似的还有：x1=x2=x4，x2=x3=x4，x1=x3=x4，x1=x2且x3=x4，x2=x3且x1=x4。
第一步的答案中应该减去1个 x1=x2=x3=x4 但是在第二步中减去了4个 x1=x2=x3=x4，第三步中又加了6个 x1=x2=x3=x4，所以总共加了2个 x1=x2=x3=x4，最终应该减去3个 x1=x2=x3=x4 的情况。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const int mod=1e9+7; int main() { int n; while(~scanf("%d",&n)) { ll l1,r1,l2,r2,l3,r3,l4,r4; ll mal_1,mir_1,mal_2,mir_2; while(n--) { scanf("%lld%lld%lld%lld%lld%lld%lld%lld",&l1,&r1,&l2,&r2,&l3,&r3,&l4,&r4); // All // + mod：是因为可能会有重复，所以有可能会减多了导致有负数情况 // rs - ...的时候就无需 mod 了 ll rs=(r1-l1+1)*(r2-l2+1)%mod*(r3-l3+1)%mod*(r4-l4+1)%mod; // 1==2 mal_1=max(l1,l2), mir_1=min(r1,r2); if(mir_1>=mal_1) rs=(rs-(mir_1-mal_1+1)*(r3-l3+1)%mod*(r4-l4+1)%mod+mod)%mod; // 2==3 mal_1=max(l2,l3), mir_1=min(r2,r3); if(mir_1>=mal_1) rs=(rs-(mir_1-mal_1+1)*(r1-l1+1)%mod*(r4-l4+1)%mod+mod)%mod; // 3==4 mal_1=max(l3,l4), mir_1=min(r3,r4); if(mir_1>=mal_1) rs=(rs-(mir_1-mal_1+1)*(r1-l1+1)%mod*(r2-l2+1)%mod+mod)%mod; // 4==1 mal_1=max(l4,l1), mir_1=min(r4,r1); if(mir_1>=mal_1) rs=(rs-(mir_1-mal_1+1)*(r2-l2+1)%mod*(r3-l3+1)%mod+mod)%mod; // 1==2==3 mal_1=max(l1,max(l2,l3)), mir_1=min(r1,min(r2,r3)); if(mir_1>=mal_1) rs=(rs+(mir_1-mal_1+1)*(r4-l4+1)%mod)%mod; // 1==2==4 mal_1=max(l1,max(l2,l4)), mir_1=min(r1,min(r2,r4)); if(mir_1>=mal_1) rs=(rs+(mir_1-mal_1+1)*(r3-l3+1)%mod)%mod; // 2==3==4 mal_1=max(l4,max(l2,l3)), mir_1=min(r4,min(r2,r3)); if(mir_1>=mal_1) rs=(rs+(mir_1-mal_1+1)*(r1-l1+1)%mod)%mod; // 1==3==4 mal_1=max(l1,max(l3,l4)), mir_1=min(r1,min(r3,r4)); if(mir_1>=mal_1) rs=(rs+(mir_1-mal_1+1)*(r2-l2+1)%mod)%mod; // 1==2 && 3==4 mal_1=max(l1,l2), mir_1=min(r1,r2); mal_2=max(l3,l4), mir_2=min(r3,r4); if(mir_1>=mal_1 && mir_2>=mal_2) rs=(rs+(mir_1-mal_1+1)*(mir_2-mal_2+1)%mod)%mod; // 2==3 && 1==4 mal_1=max(l2,l3), mir_1=min(r2,r3); mal_2=max(l1,l4), mir_2=min(r1,r4); if(mir_1>=mal_1 && mir_2>=mal_2) rs=(rs+(mir_1-mal_1+1)*(mir_2-mal_2+1)%mod)%mod; // 1==2==3==4 mal_1=max(max(l1,l2),max(l3,l4)), mir_1=min(min(r1,r2),min(r3,r4)); if(mir_1>=mal_1) rs=(rs-(mir_1-mal_1+1)*3%mod+mod)%mod; printf("%lld\n",rs); } } return 0; }
