省赛 F: Four-tuples

时间限制: 10 Sec 内存限制: 128 MB

题目描述

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 

容斥定理，先把每一部分的交集求出来，然后根据公式求。

AC代码；

include <bits/stdc++.h>
using namespace std;

int bijiao[20];//每次比较时记录四个坐标

int jiaoji(int x1,int x2,int y1,int y2)//求交集

{if(x2<y1||x2>y2)

{

    return 0;

}

else

{

   bijiao[0]=x1;

   bijiao[1]=x2;

   bijiao[2]=y1;

   bijiao[3]=y2;

   sort(bijiao,bijiao+4);
   return bijiao[2]-bijiao[1]+1;
}
}

int main()

{

int T;

int a[5][2];

long long int b[100][100];

scanf("%d",&T);

while(T--)

{ scanf("%d%d%d%d%d%d%d%d",&a[0][0],&a[0][1],&a[1][0],&a[1][1],&a[2][0],&a[2][1],&a[3][0],&a[3][1]);

 b[0][1]=a[0][1]-a[0][0]+1;
 b[0][2]=a[1][1]-a[1][0]+1;
 b[0][3]=a[2][1]-a[2][0]+1;
 b[0][4]=a[3][1]-a[3][0]+1;
 b[1][2]=jiaoji(a[0][0],a[0][1],a[1][0],a[1][1]);
 b[1][3]=jiaoji(a[0][0],a[0][1],a[2][0],a[2][1]);
 b[1][4]=jiaoji(a[0][0],a[0][1],a[3][0],a[3][1]);
 b[2][3]=jiaoji(a[1][0],a[1][1],a[2][0],a[2][1]);
 b[2][4]=jiaoji(a[1][0],a[1][1],a[3][0],a[3][1]);
 b[3][4]=jiaoji(a[2][0],a[2][1],a[3][0],a[3][1]);
 if(b[1][2]==0)
 {
     b[12][34]=0;
 }
 else
 {
    int p=jiaoji(a[0][0],a[0][1],a[1][0],a[1][1]);
    b[12][34]=jiaoji(bijiao[2],bijiao[1],a[2][0],a[2][1]);
 }
 if(b[1][3]==0)
 {
     b[13][42]=0;
 }
 else
 {
    int p=jiaoji(a[0][0],a[0][1],a[2][0],a[2][1]);
    b[13][42]=jiaoji(bijiao[2],bijiao[1],a[3][0],a[3][1]);
 }
 if(b[1][2]==0)
 {
     b[12][43]=0;
 }
 else
 {
    int p=jiaoji(a[0][0],a[0][1],a[1][0],a[1][1]);
    b[12][43]=jiaoji(bijiao[2],bijiao[1],a[3][0],a[3][1]);
 }
  if(b[2][3]==0)
 {
     b[23][41]=0;
 }
 else
 {
    int p=jiaoji(a[1][0],a[1][1],a[2][0],a[2][1]);
    b[23][41]=jiaoji(bijiao[2],bijiao[1],a[3][0],a[3][1]);
 }
 if(b[12][34]==0)
 {
     b[11][11]=0;
 }
 else
 {
    int p=jiaoji(a[0][0],a[0][1],a[1][0],a[1][1]);
    b[12][34]=jiaoji(bijiao[2],bijiao[1],a[2][0],a[2][1]);

    b[11][11]=jiaoji(bijiao[2],bijiao[1],a[3][0],a[3][1]);

 }
 long long int s;

s=(((b[0][4]*b[0][1]%1000000007)*b[0][2]%1000000007)*b[0][3]%1000000007);

 s=(s-((b[1][2]*b[0][3]%1000000007)*b[0][4]%1000000007)+1000000007)%1000000007;

 s=(s-((b[1][4]*b[0][2]%1000000007)*b[0][3]%1000000007)-((b[2][3]*b[0][1]%1000000007)*b[0][4]%1000000007)+1000000007)%1000000007;
 s=(s-((b[3][4]*b[0][1]%1000000007)*b[0][2]%1000000007)+1000000007)%1000000007;
 s=(s+(b[12][34]*b[0][4])%1000000007)%1000000007;
 s=(s+b[1][2]*b[3][4]%1000000007)%1000000007;
 s=(s+b[2][3]*b[1][4]%1000000007)%1000000007;
 s=(s+b[12][43]*b[0][3])%1000000007;
 s=(s+b[13][42]*b[0][2])%1000000007;
 s=(s+b[23][41]*b[0][1])%1000000007;
 s=(s-b[11][11]*3+1000000007)%1000000007;
 printf("%lld
",s);
} return 0; }