联赛模拟测试12 C. sum 莫队+组合数
题目描述
分析
\(80\) 分的暴力都打出来了还是没有想到莫队
首先对于 \(s[n][m]\) 我们可以很快地由它推到 \(s[n][m+1]\) 和 \(s[n][m-1]\)
即 \(s[n][m+1]=s[n][m]+C_n^{m+1}\)
\(s[n][m-1]=s[n][m]-C_n^m\)
然后我们考虑怎么由 \(s[n][m]\) 推到 \(s[n-1][m]\) 和 \(s[n+1][m]\)
其实画出杨辉三角观察性质即可
摘自 \({\color{black}{M}}{\color{red}{idoria7}}\)的博客
\(\Huge \%\%\%谢队\)
这样，我们可以 \(O(1)\) 转移，然后把 \(m\) 看成 \(l\) ,把 \(n\) 看成 \(r\)，套一个莫队的板子
代码
#include<cstdio>
#include<algorithm>
#include<cmath>
#define rg register
const int maxn=1e6+5;
const int mod=1e9+7;
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
int haha,q,n,m,ny[maxn],jc[maxn],jcc[maxn];
int getC(int nn,int mm){
return 1LL*jc[nn]*jcc[mm]%mod*jcc[nn-mm]%mod;
}
int blo,shuyu[maxn],ans[maxn];
struct asd{
int l,r,id;
asd(){}
asd(int aa,int bb,int cc){
l=aa,r=bb,id=cc;
}
}b[maxn];
bool cmp(asd aa,asd bb){
if(shuyu[aa.l]==shuyu[bb.l]) return aa.r<bb.r;
return aa.l<bb.l;
}
int main(){
haha=read();
ny[1]=1;
for(rg int i=2;i<maxn;i++){
ny[i]=1LL*(mod-mod/i)*ny[mod%i]%mod;
}
jc[0]=jcc[0]=1;
for(rg int i=1;i<maxn;i++){
jc[i]=1LL*jc[i-1]*i%mod;
jcc[i]=1LL*jcc[i-1]*ny[i]%mod;
}
q=read();
rg int aa,bb,mmax=0;
for(rg int i=1;i<=q;i++){
aa=read(),bb=read();
b[i]=asd(bb,aa,i);
mmax=std::max(mmax,bb);
}
blo=sqrt(mmax);
for(rg int i=1;i<=mmax;i++){
shuyu[i]=(i-1)/blo+1;
}
std::sort(b+1,b+1+q,cmp);
int l=1,r=0,nans=1;
for(rg int i=1;i<=q;i++){
while(l>b[i].l){
nans=(nans-getC(r,l)+mod)%mod;
l--;
}
while(r<b[i].r){
nans=(nans*2%mod-getC(r,l)+mod)%mod;
r++;
}
while(l<b[i].l){
nans=(nans+getC(r,l+1))%mod;
l++;
}
while(r>b[i].r){
nans=1LL*(nans+getC(r-1,l))%mod*ny[2]%mod;
r--;
}
ans[b[i].id]=nans;
}
for(rg int i=1;i<=q;i++){
printf("%d\n",ans[i]);
}
return 0;
}
版权声明：本文为liuchanglc原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。