HDU5139:Formula(找规律+离线处理）-白红宇

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

阅读量：6480 次

发布时间：2019-06-23

本文共 1233 字，大约阅读时间需要 4 分钟。

Problem Description

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]

Output

For each n，output f(n) in a single line.

Sample Input

100

Sample Output

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 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #include 
           
            #include 
            
             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