本文共 3579 字，大约阅读时间需要 11 分钟。

Problem F.Four-tuples

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

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).

Output

For each test case, output one line containing one integer, representing the answer.

Sample Input

Sample Output

题目大意：给你四个区间，要求每个区间选一个数组成一个四元组（x1,x2,x3,x4）要求： 

1. x1≠x2，x2≠x3，x3≠x4，x4≠x1
2. li<=xi<=ri

解题思路：（容斥原理）

1. 先将四个区间长度的乘积作为答案。
2. 分别减去 x1=x2，x2=x3，x3=x4，x4=x1 四种情况的组合数量（每种情况中未提及的变量在其区间中任选，即统计答案时直接乘区间长度） 。
3. 因为减去 x1=x2 和 x2=x3 时会重复减去 x1=x2=x3 的情况，所以要加回来，类似的还有：x1=x2=x4，x2=x3=x4，x1=x3=x4，x1=x2且x3=x4，x2=x3且x1=x4。
4. 第一步的答案中应该减去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
   
    #include
    
     #define mem(a,b) memset(a,b,sizeof a);#define INF 0x3f3f3f3fusing 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;}
    
   

转载地址：https://lux-sun.blog.csdn.net/article/details/81078186 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！