「AT987」高橋君

传送门

Luogu

第一道 AtCoder 的题解。

联动一波asuldb。

「啊这题怎么做啊。看起来好难啊。不会啊。」

「我们来蒙一个做法吧。比如说就莫队了！」

$$\sum_{i=0}^{m+1}C_{n}^{i}=\sum_{i=0}^{m}C_{n}^{i}+C_{n}^{m+1}$$ $$\sum_{i=0}^{m}C_{n+1}^{i}=\sum_{i=0}^{m}(C_{n}^{i}+C_{n}^{i-1})=\sum_{i=0}^{m}C_{n}^{i}+\sum_{i=0}^{m-1}C_{n}^{i-1}=2\sum_{i=0}^{m}C_{n}^{i}-C_{n}^{m}$$

这是左右端点向右移动的情况。向左移动就反过来。

就这样。

但是不知道为什么奇偶性排序会 WA。

好短啊 QAQ

#include<cstdio>
#include<cmath>
#include<algorithm>
#define re register
#define maxn 100000
#define mod 1000000007
#define id(a) (a/sq+1)
#define C(n,m) (1LL*fac[n]*inv[m]%mod*inv[n-m]%mod)

namespace cltstream{
     #define size 1048576
     char cltin[size+1],*ih=cltin,*it=cltin;
     inline char gc(){
         #ifdef ONLINE_JUDGE
             if(ih==it){
                 it=(ih=cltin)+fread(cltin,1,size,stdin);
                 if(ih==it)
                     return EOF;
             }
             return *ih++;
         #else
             return getchar();
         #endif
     }

     char cltout[size+1],*oh=cltout,*ot=cltout+size;
     inline void pc(char c){
         if(oh==ot){
             fwrite(cltout,1,size,stdout);
             oh=cltout;
         }
        *oh++=c;
     }
     #define clop() fwrite(cltstream::cltout,1,cltstream::oh-cltstream::cltout,stdout),cltstream::oh=cltstream::cltout
     #undef size

     template <typename _tp>
     inline void read(_tp& x){
         int sn=1;
         char c=gc();
         for(;c!=45&&(c<48||c>57)&&c!=EOF;c=gc());
         if(c==45&&c!=EOF)
             sn=-1,c=gc();
         for(x=0;c>=48&&c<=57&&c!=EOF;x=(x<<3)+(x<<1)+(c^48),c=gc());
         x*=sn;
     }

     template <typename _tp>
     inline void write(_tp x,char text=-1){
         if(x<0)
             pc(45),x=-x;
         if(!x)
             pc(48);
         else{
             int digit[22];
             for(digit[0]=0;x;digit[++digit[0]]=x%10,x/=10);
             for(;digit[0];pc(digit[digit[0]--]^48));
         }
         if(text>=0)
             pc(text);
     }
}

int n,sq;
int fac[maxn+1],inv[maxn+1];
struct Query{
     int t,l,r;
};
Query q[maxn+1];
int ans[maxn+1];

inline bool operator<(re Query p1,re Query p2){
     return id(p1.l)==id(p2.l)?p1.r<p2.r:p1.l<p2.l;
}

int main(){
     fac[0]=inv[0]=fac[1]=inv[1]=1;
     for(re int i=2;i<=maxn;++i)
         inv[i]=(mod-1LL*mod/i*inv[mod%i]%mod)%mod;
     for(re int i=2;i<=maxn;++i){
         fac[i]=1LL*fac[i-1]*i%mod;
         inv[i]=1LL*inv[i-1]*inv[i]%mod;
     }
     cltstream::read(n);
     sq=maxn/sqrt(n);
     for(re int i=1;i<=n;++i){
         q[i].t=i;
         cltstream::read(q[i].r);
         cltstream::read(q[i].l);
     }
     std::sort(q+1,q+n+1);
     re int L=0,R=0,res=1;
     for(re int i=1;i<=n;++i){
         for(;R<q[i].r;res=(2*res-C(R,L)+mod)%mod,++R);
         for(;R>q[i].r;--R,res=inv[2]*(res+C(R,L))%mod);
         for(;L<q[i].l;++L,res=(res+C(R,L))%mod);
         for(;L>q[i].l;res=(res-C(R,L)+mod)%mod,--L);
         ans[q[i].t]=res;
     }
     for(re int i=1;i<=n;++i)
         cltstream::write(ans[i],10);
     clop();
     return 0;
}