Liers 树状数组+中国剩余定理

Liers

Time Limit: 14000/7000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

有N个人，其中有若干个人一起参加了舞会，现在想知道哪些人有可能参加了舞会，你问了N个人，第i个人说参加舞会的人数在[Li,Ri]区间的一个数，问有多少种合法的舞会人数方案？所谓合法方案是指，参加舞会的所有人说的都是真话，即参加舞会的人中，舞会总人数符合所有参加舞会的人的话语(不一定符合没有参加舞会的人的话语)，即在其区间中。假设参加了舞会的人说的都是真话。

Input

多组数据，每组数据：

第一行，N(1 <= N <= 10^6)，总人数

从2到N + 1行，每行两个正整数，L,R，表示第i个人说的，舞会总人数为[L,R]中的一个数 -2^31 <= L,R <= 2^31 - 1(int)

Output

每组数据输出一行，总合法数 % 20140717

Sample Input

Sample Output

3
6

Hint

第二个样例说明，舞会可能只有一个人参加，这样由3种情况，1或者2或者3，也可能2个人参加，(1,2)或(1,3)或(2,3)，注意，一个合理的舞会至少需要有一个人

  1 #include <iostream>
  2 #include <stdio.h>
  3 #include <math.h>
  4 #include <string.h>
  5 #include <algorithm>
  6 using namespace std;
  7 #define mod 20140717LL
  8 #define ll long long
  9 typedef struct people
 10 {
 11     int l,r;
 12 } people;
 13 people p[1000001];
 14 int b[1000001],n;
 15 short int a1[46][46]= {0},a2[110][110]= {0},a3[4599][4599]= {0};
 16 void init()
 17 {
 18     int i,j;
 19     a1[0][0]=a2[0][0]=a3[0][0]=1;
 20     for(i=1; i<4599; i++)
 21     {
 22         a3[i][i]=a3[i][0]=1;
 23         for(j=1; j<i; j++)
 24             a3[i][j]=a3[i-1][j-1]+a3[i-1][j],a3[i][j]%=4591;
 25     }
 26     for(i=1; i<110; i++)
 27     {
 28         a2[i][i]=a2[i][0]=1;
 29         for(j=1; j<i; j++)
 30             a2[i][j]=a2[i-1][j-1]+a2[i-1][j],a2[i][j]%=107;
 31     }
 32     for(i=1; i<46; i++)
 33     {
 34         a1[i][i]=a1[i][0]=1;
 35         for(j=1; j<i; j++)
 36             a1[i][j]=a1[i-1][j-1]+a1[i-1][j],a1[i][j]%=41;
 37     }
 38 }
 39 int lowbit(int x)
 40 {
 41     return x&(-x);
 42 }
 43 void update(int x,int z)
 44 {
 45     while(x>0)
 46     {
 47         b[x]+=z;
 48         x-=lowbit(x);
 49     }
 50 }
 51 int query(int x)
 52 {
 53     int sum=0;
 54     while(x<=n)
 55     {
 56         sum+=b[x];
 57         x+=lowbit(x);
 58     }
 59     return sum;
 60 }
 61 int fun1(int m,int x,int y)
 62 {
 63     int ans=1;
 64     while(x)
 65     {
 66         if(y==41)
 67             ans*=a1[m%y][x%y];
 68         else if(y==107)
 69             ans*=a2[m%y][x%y];
 70         else ans*=a3[m%y][x%y];
 71         m/=y,x/=y;
 72     }
 73     return ans;
 74 }
 75 int fun(int m,int x)
 76 {
 77     ll m1,m2,m3;
 78     m1=fun1(m,x,41);
 79     m2=fun1(m,x,107);
 80     m3=fun1(m,x,4591);
 81     int ans=((m1*8842266LL)%mod+(m2*1129386LL)%mod+(m3*10169066LL)%mod)%mod;
 82     return ans;
 83 }
 84 int main()
 85 {
 86     // freopen("in.txt","r",stdin);
 87     init();
 88     int i,j,ans,m;
 89     while(scanf("%d",&n)!=EOF)
 90     {
 91         for(i=0; i<n; i++)
 92         {
 93             scanf("%d%d",&p[i].l,&p[i].r);
 94             if(p[i].l<=0)p[i].l=1;
 95             if(p[i].l>n)p[i].r=n;
 96             if(p[i].r<=0)p[i].r=1;
 97             if(p[i].r>n)p[i].r=n;
 98         }
 99         memset(b,0,sizeof(b));
100         for(i=0; i<n; i++)
101         {
102             update(p[i].r,1);
103             update(p[i].l-1,-1);
104         }
105         ans=0;
106         for(i=1; i<=n; i++)
107         {
108             m=query(i);
109             if(m>=i)
110                 ans+=fun(m,i),ans%=mod;
111         }
112         printf("%d
",ans%mod);
113     }
114 
115 }

View Code