http://www.zybbs.org/JudgeOnline/problem.php?id=1300

刷了20+次还是刷不到tbl的160MS……OrzXTY……

此题是求C(N,M)的前3位和后9位……前3位很好求，把各个数的 log10加起来，最后如果得到a.b，那么答案就是10^(a.b)=(10^0.b)*10^a，其中a是整数，所以只要把a替换成2然后pow就可以了。

后9位一开始脑残，把每个数分解质因数然后存到数组里最后乘起来，结果速度爆慢（3S+）。想了一天突然发现自己犯傻了……其实方法很简单，答案是N!/M!/(N-M)!，对于素数a，在N!中出现了N/a+N/a^2+...次，后面两个也同理。这样只要对于每个素数算一次就可以了……（我想所有人应该都一下子就想到了吧……我太弱了）如果还觉得慢，可以在乘到一定程度（我取10^7和10^6时间都是172MS）的时候再取log10。

NZM神犇说可以用中国剩余定理+EXGCD做到更低的时间复杂度……膜拜……

我试了试中国剩余定理+EXGCD，反而慢了……T^T

#include <stdio.h>
#include <math.h>
int n,m;
long long ans=1;
_Bool p[1000001];
main(){
	double k=0,f=1;int i,j,x,l,c,s;
	scanf("%d%d",&n,&m);if(m>n-m)m=n-m;
	for(i=2;i<=n;i++)if(!p[i]){
		for(j=n,x=n-m,l=m;j;){
			for(c=(j/=(s=i))-(x/=i)-(l/=i)<<1;c>>=1;s*=s)if(c&1)ans*=s;
			ans%=1000000000000LL;
		}if(i<=1000)for(j=i*i;j<=n;j+=i)p[j]=1;
	}for(i=1;i<=m;i++){
		if(f>10000000){k+=log10(f);f=1;}
		f=f*(n-m+i)/i;
	}if((k+=log10(f))<13)printf("%lld\n",ans);
	else printf("%d...%09lld\n",(int)(pow(10,k-floor(k)+2)+1e-5),ans%1000000000LL);
	return 0;
}

• inline
• block