2018 多校
[ 2018 Multi-University Training Contest 4 ] [ HDU6336 ] E Matrix from Arrays

[ 2018 Multi-University Training Contest 4 ] [ HDU6333 ] Harvest of Apples

Zarxdy34 posted @ 2018年8月01日 20:41 in HDU with tags 莫队 , 47 阅读

        题目大意:求\(\sum_{i=0}^m{C_n^i}\),数据组数\(T \leq 10^5 \),\( 1 \leq m \leq n \leq 10^5 \)。

        题解:公式搞了半天搞不出来,结果是莫队做...

        m加减1很容易处理出来,利用\(C_{n+1}^m = C_n^{m-1} + C_n^m\)也可以很容易搞出n加减1的情况。

 

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10,Bsize=300,mo=1e9+7;

struct Query
{
	int n,m,id;
}Q[maxn];

bool cmpnm(const Query &a,const Query &b) {
	if (a.n/Bsize != b.n/Bsize) return a.n/Bsize < b.n/Bsize;
	return a.m<b.m;
}

long long inv[maxn];
int ans[maxn];
int T;

int main()
{
	inv[0]=inv[1]=1;
	for (int i=2;i<maxn;i++) inv[i]=(mo-mo/i)*inv[mo%i]%mo;
	scanf("%d",&T);
	for (int i=1;i<=T;i++) scanf("%d%d",&Q[i].n,&Q[i].m),Q[i].id=i;
	sort(Q+1,Q+1+T,cmpnm);
	for (long long i=1,n=0,m=0,nowc=1,res=1;i<=T;i++)
	{
		long long nown=Q[i].n,nowm=Q[i].m;
		while (n<nown)
			res=(res*2-nowc+mo)%mo,nowc=nowc*(n+1)%mo*inv[n+1-m]%mo,n+=1;
		while (n>nown)
			nowc=nowc*(n-m)%mo*inv[n]%mo,res=(res+nowc)%mo*inv[2]%mo,n-=1;
		while (m<nowm)
			nowc=nowc*(n-m)%mo*inv[m+1]%mo,res=(res+nowc)%mo,m+=1;
		while (m>nowm)
			res=(res-nowc+mo)%mo,nowc=nowc*m%mo*inv[n-m+1]%mo,m-=1;
		ans[Q[i].id]=res;
	}
	for (int i=1;i<=T;i++) printf("%d\n",ans[i]);
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter