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)，注意，一个合理的舞会至少需要有一个人

 #include <iostream>

 #include <stdio.h>

 #include <math.h>

 #include <string.h>

 #include <algorithm>

 using namespace std;

 #define mod 20140717LL

 #define ll long long

 typedef struct people

 {

     int l,r;

 } people;

 people p[];

 int b[],n;

 short int a1[][]= {},a2[][]= {},a3[][]= {};

 void init()

 {

     int i,j;

     a1[][]=a2[][]=a3[][]=;

     for(i=; i<; i++)

     {

         a3[i][i]=a3[i][]=;

         for(j=; j<i; j++)

             a3[i][j]=a3[i-][j-]+a3[i-][j],a3[i][j]%=;

     }

     for(i=; i<; i++)

     {

         a2[i][i]=a2[i][]=;

         for(j=; j<i; j++)

             a2[i][j]=a2[i-][j-]+a2[i-][j],a2[i][j]%=;

     }

     for(i=; i<; i++)

     {

         a1[i][i]=a1[i][]=;

         for(j=; j<i; j++)

             a1[i][j]=a1[i-][j-]+a1[i-][j],a1[i][j]%=;

     }

 }

 int lowbit(int x)

 {

     return x&(-x);

 }

 void update(int x,int z)

 {

     while(x>)

     {

         b[x]+=z;

         x-=lowbit(x);

     }

 }

 int query(int x)

 {

     int sum=;

     while(x<=n)

     {

         sum+=b[x];

         x+=lowbit(x);

     }

     return sum;

 }

 int fun1(int m,int x,int y)

 {

     int ans=;

     while(x)

     {

         if(y==)

             ans*=a1[m%y][x%y];

         else if(y==)

             ans*=a2[m%y][x%y];

         else ans*=a3[m%y][x%y];

         m/=y,x/=y;

     }

     return ans;

 }

 int fun(int m,int x)

 {

     ll m1,m2,m3;

     m1=fun1(m,x,);

     m2=fun1(m,x,);

     m3=fun1(m,x,);

     int ans=((m1*8842266LL)%mod+(m2*1129386LL)%mod+(m3*10169066LL)%mod)%mod;

     return ans;

 }

 int main()

 {

     // freopen("in.txt","r",stdin);

     init();

     int i,j,ans,m;

     while(scanf("%d",&n)!=EOF)

     {

         for(i=; i<n; i++)

         {

             scanf("%d%d",&p[i].l,&p[i].r);

             if(p[i].l<=)p[i].l=;

             if(p[i].l>n)p[i].r=n;

             if(p[i].r<=)p[i].r=;

             if(p[i].r>n)p[i].r=n;

         }

         memset(b,,sizeof(b));

         for(i=; i<n; i++)

         {

             update(p[i].r,);

             update(p[i].l-,-);

         }

         ans=;

         for(i=; i<=n; i++)

         {

             m=query(i);

             if(m>=i)

                 ans+=fun(m,i),ans%=mod;

         }

         printf("%d\n",ans%mod);

     }

 }

秒客网