Four-tuples（2018山东省赛 F）

问题 F: Four-tuples

时间限制: 10 Sec  内存限制: 128 MB
提交: 13  解决: 8
[提交][状态][讨论版][命题人:admin]

题目描述

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.

样例输入

1
1 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:

#include <bits/stdc++.h>
 
using 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
",(sum-ant+mod)%mod);
    }
    return 0;
}