1300: [LLH邀请赛]大数计算器 - #include <Seter> - using namespace Orz;

1300: [LLH邀请赛]大数计算器

Seter posted @ 2011年9月17日 18:15 in BZOJ with tags Enumeration NumberTheory , 2433 阅读

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

RunID User Problem Result Memory Time Language Code Length Submit Time
152924 Seter 1300 Accepted 1744 kb 172 ms C/Edit 637 B 2011-09-17 17:43:20

刷了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;
}
By Seter
  • 无匹配

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee