Submission #4028457
Source Code Expand
#include<bits/stdc++.h> using namespace std; #define p 1000000007ll #define N 200005 #define ll long long ll len,l,r,ans,inv[N],mul[N],mulinv[N],Ans[N]; struct node{ ll l,r,id; }; node q[N]; bool cmp(node a,node b){return(a.l/len)^(b.l/len)?a.l<b.l:((a.l/len)&1)?a.r<b.r:a.r>b.r;} ll C(ll n,ll m){return((mul[n]*mulinv[m])%p*mulinv[n-m])%p;} void change1(){ans=(((2*ans)%p-C(l,r))%p+p)%p;} void change2(){ans=((inv[2]*((ans+C(l,r))%p))%p+p)%p;} void change3(){ans=((ans+C(l,r))%p+p)%p;} void change4(){ans=((ans-C(l,r))%p+p)%p;} int main() { scanf("%lld",&n); len=sqrt(n); int i; inv[1]=1,mul[0]=mulinv[0]=1; for(i=2;i<=100000;i++)inv[i]=(-(p/i)%p*inv[p%i]%p+p)%p; for(i=1;i<=100000;i++) { mul[i]=(mul[i-1]*i)%p; mulinv[i]=(mulinv[i-1]*inv[i])%p; } for(i=1;i<=n;i++) { scanf("%lld%lld",&q[i].l,&q[i].r); q[i].id = i; } sort(q+1,q+n+1,cmp); l=1;r=0;ans=1; for(i=1;i<=n;i++) { while (l<q[i].l){change1();l++;} while (l>q[i].l){l--;change2();} while (r<q[i].r){r++;change3();} while (r>q[i].r){change4();r--;} Ans[q[i].id]=ans; } for(i=1;i<=n;i++) printf("%lld\n",Ans[i]); return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - 高橋君 |
User | luogu_bot2 |
Language | C++ (GCC 5.4.1) |
Score | 0 |
Code Size | 1236 Byte |
Status | CE |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:19:19: error: ‘n’ was not declared in this scope scanf("%lld",&n); ^ ./Main.cpp:31:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%lld%lld",&q[i].l,&q[i].r); ^