首页 > 代码库 > HDU5139:Formula(找规律+离线处理)
HDU5139:Formula(找规律+离线处理)
http://acm.hdu.edu.cn/showproblem.php?pid=5139
Problem Description
f(n)=(∏i=1nin−i+1)%1000000007
You are expected to write a program to calculate f(n) when a certain n is given.
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]
1≤n≤10000000
Output
For each n,output f(n) in a single line.
Sample Input
2
100
Sample Output
2
148277692
官方题解:
找规律f(1)=1f(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数目。
题目解析:以前根本不知道题目可以这么做,又学了一样新东西,离线处理。
#include <iostream>#include <stdio.h>#include <math.h>#include <queue>#include <map>#include <stdlib.h>#include <algorithm>#include <string.h>const int mod=1000000007;using namespace std;int n,tt;struct node{ int id,x,sum;} q[100010];int cmp1(const void *a,const void *b){ struct node *aa=(struct node *)a; struct node *bb=(struct node *)b; return aa->x-bb->x;}int cmp2(const void *a,const void *b){ struct node *aa=(struct node *)a; struct node *bb=(struct node *)b; return aa->id-bb->id;}int main(){ tt=0; __int64 s=1,s2=1; while(scanf("%d",&n)!=EOF) { q[tt].id=tt; q[tt++].x=n; } qsort(q,tt,sizeof(q[0]),cmp1); for(int i=0,j=2; i<tt; i++) { for(; j<=q[i].x; j++) { s=(s*j)%mod; s2=(s*s2)%mod; } q[i].sum=s2; } qsort(q,tt,sizeof(q[0]),cmp2); for(int i=0; i<tt; i++) printf("%d\n",q[i].sum); return 0;}
HDU5139:Formula(找规律+离线处理)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。