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