问题 F: Four-tuples
时间限制: 10 Sec 内存限制: 128 MB提交: 13 解决: 8[][][][命题人:]题目描述
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 10^9+7 before output.
输入
The input consists of several test cases. The first line gives the number of test cases, T(1≤ T≤ 10^6). For each test case, the input contains one line with 8 integers l1,r1,l2, r2, l3,r3,l4,r4(1≤ li≤ ri≤ 10^9)
输出
For each test case, output one line containing one integer, representing the answer.
样例输入
11 1 2 2 3 3 4 4
样例输出
1 题意很简单，这是一道容斥定理题，其实也挺简单的，，，（然而自己菜，容斥公式忘了，翻书找到的容斥竟然是有错的，然后最后一直debug....也没发现问题，最后队友说交一发试试，没想到返回yes） 吃惊！！！！！ 设事件A为x1!=x2 ,事件B 为x2!=x3 ,事件C 为 x3!=x4 事件D 为 x4!=x1 问题要求：|A∩B∩C∩D| 可以转换成|U|-|A'∪B'∪C'∪D'| 即求 |A'∪B'∪C'∪D'| 就行，容斥定理
c++ code:
#includeusing namespace std; const int mod=1e9+7;typedef long long ll;ll Query(ll l1,ll r1,ll l2,ll r2){ ll l=max(l1,l2),r=min(r1,r2); return r-l+1>0?r-l+1:0;}ll Query2(ll l1,ll r1,ll l2,ll r2,ll l3,ll r3){ ll l=max(l1,max(l2,l3)),r=min(r1,min(r2,r3)); return r-l+1>0?r-l+1:0;}ll Query3(ll l1,ll r1,ll l2,ll r2,ll l3,ll r3,ll l4,ll r4){ ll l=max(max(l1,l2),max(l3,l4)),r=min(min(r1,r2),min(r3,r4)); return r-l+1>0?r-l+1:0;}int main(){ int t; ll l1,r1,l2,r2,l3,r3,l4,r4; scanf("%d",&t); while(t--) { scanf("%lld%lld%lld%lld%lld%lld%lld%lld",&l1,&r1,&l2,&r2,&l3,&r3,&l4,&r4); ll sum=1; sum=sum*(r1-l1+1)%mod; sum=sum*(r2-l2+1)%mod; sum=sum*(r3-l3+1)%mod; sum=sum*(r4-l4+1)%mod; ll ant=0; ant=(ant+Query(l1,r1,l2,r2)%mod*(r3-l3+1)%mod*(r4-l4+1)%mod)%mod; ant=(ant+Query(l2,r2,l3,r3)%mod*(r1-l1+1)%mod*(r4-l4+1)%mod)%mod; ant=(ant+Query(l3,r3,l4,r4)%mod*(r1-l1+1)%mod*(r2-l2+1)%mod)%mod; ant=(ant+Query(l4,r4,l1,r1)%mod*(r3-l3+1)%mod*(r2-l2+1)%mod)%mod; ant=(ant-Query2(l1,r1,l2,r2,l3,r3)*(r4-l4+1)%mod+mod)%mod; ant=(ant-Query(l1,r1,l2,r2)*Query(l3,r3,l4,r4)%mod+mod)%mod; ant=(ant-Query2(l1,r1,l2,r2,l4,r4)*(r3-l3+1)%mod+mod)%mod; ant=(ant-Query2(l2,r2,l3,r3,l4,r4)*(r1-l1+1)%mod+mod)%mod; ant=(ant-Query(l2,r2,l3,r3)*Query(l1,r1,l4,r4)%mod+mod)%mod; ant=(ant-Query2(l1,r1,l3,r3,l4,r4)*(r2-l2+1)%mod+mod)%mod; ant=(ant+3*Query3(l1,r1,l2,r2,l3,r3,l4,r4)%mod+mod)%mod; printf("%lld\n",(sum-ant+mod)%mod); } return 0;}