首页 > 代码库 > HDU 5139 Formula 离线处理
HDU 5139 Formula 离线处理
点击打开链接
Formula
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 361 Accepted Submission(s): 151
Problem Description
You are expected to write a program to calculate f(n) when a certain n is given.
Input
Multi test cases (about 100000), every case contains an integer n in a single line.
Please process to the end of file.
[Technical Specification]
1≤n≤10000000
Please process to the end of file.
[Technical Specification]
Output
For each n,output f(n) in a single line.
Sample Input
2 100
Sample Output
2 148277692
Source
BestCoder Round #21
找规律
f(1)=1
f(2)=1*1*2=(1)*(1*2)=1!*2!
f(3)=1*1*1*2*2*3=(1)*(1*2)*(1*2*3)=1!*2!*3!
式子可以简化为 f(n)=∏i=1n(n!)%MOD ,直接打表不行,会超内存,可以对数据进行离线处理。排好序之后从小到大暴力。ClogC+10000000 ,C为case数目。
//702MS 4228K #include<stdio.h> #include<string.h> #include<algorithm> #define ll __int64 #define M 1000000007 using namespace std; struct Keng { ll val; int pos; } p[100007],ans[100007]; int cmp(Keng a,Keng b) { return a.val<b.val; } int main() { ll anss=1,b=1,n; int k=0; while(scanf("%I64d",&n)!=EOF) p[++k].val=n,p[k].pos=k; sort(p+1,p+k+1,cmp); p[0].val=0; for(int i=1; i<=k; i++) { for(int j=p[i-1].val+1;j<=p[i].val;j++) { b=(b*j)%M; anss=(b*anss)%M; } ans[p[i].pos].val=anss; } for(int i=1; i<=k; i++) printf("%I64d\n",ans[i].val); return 0; }
HDU 5139 Formula 离线处理
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。