bzoj4403 序列统计 组合

       假设序列长度为n，区间为[l,r]，首先求出这一段的答案。

       对于任意一个序列，将第i个数+i，那么原来的问题就转化为了n个在[l+1,r+n]区间以内的单调递增的序列的个数。后者又相当于在[l+1...r+n]这r-l+n个数中取n个的方案数，即为C(r-l+n,n)=C(r-l+n,r-l)

       所以，答案就相当于C(r-l+1,r-l)+C(r-l+2,r-l)+...+C(r-l+n,r-l)=C(r-l+n+1,r-l+1)-C(r-l,r-l)=C(r-l+n+1,n)-1。由于模数不是很大，所以后面的答案是很容易得出的。如果知道lucas定理，会更简单一点。

AC代码如下（我这么弱，怎么会知道lucas定理呢。。。）：

#include<iostream>
#include<cstdio>
#define mod 1000003
#define ll long long
using namespace std;

int f[mod][2];
int ksm(int aa,int bb){
	int sum=1;
	for (; bb; bb>>=1){
		if (bb&1) sum=(ll)sum*aa%mod; aa=(ll)aa*aa%mod;
	}
	return sum;
}
int work(int x,int p){
	return (ll)ksm(f[mod-1][p],x/mod)*f[x%mod][p]%mod*f[x/mod][p]%mod;
}
int main(){
	int cas,i; scanf("%d",&cas);
	f[0][0]=f[0][1]=f[1][0]=f[1][1]=1;
	for (i=2; i<mod; i++){
		f[i][0]=(ll)f[i-1][0]*i%mod; f[i][1]=(ll)f[mod%i][1]*(mod-mod/i)%mod;
	}
	for (i=2; i<mod; i++) f[i][1]=(ll)f[i-1][1]*f[i][1]%mod;
	while (cas--){
		int x,y,z; scanf("%d%d%d",&x,&y,&z);
		if ((x+z-y+1)/mod>x/mod+(z-y+1)/mod) puts("1000002"); else
		printf("%d\n",((ll)work(x+z-y+1,0)*work(x,1)%mod*work(z-y+1,1)+mod-1)%mod);
	}
	return 0;
}
           

by lych

2016.1.31