首页 > 代码库 > HDU5139:Formula(找规律+离线处理)

HDU5139:Formula(找规律+离线处理)

http://acm.hdu.edu.cn/showproblem.php?pid=5139

Problem Description
f(n)=(i=1nini+1)%1000000007
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]
1n10000000
 
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(找规律+离线处理)