首页 > 代码库 > Liers 树状数组+中国剩余定理

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

2024-07-12 18:21:33   218人阅读

Liers

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

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

31 11 11 130 20 20 2

Sample Output

36

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\n",ans%mod);113     }114 115 }
View Code

 


联系
我们