hdu 5139 (离线处理) - c++编程基础

TOP

hdu 5139 (离线处理)

2015-11-21 01:02:26 来源: 作者: 【大中小】浏览:2次

Tags：hdu 5139 处理

题意：

f(n)=(∏i=1nin?i+1)%1000000007
You are expected to write a program to calculate f(n) when a certain n is given.

思路：

写出前几项，就很容易得出递推式。但是因为n的数据范围是1~10000000，而内存给的小

，所以并不能直接打表（MLE）

采用离线处理——先读完，再一次性输出。

中间采取了一点小技巧，先把所有读入的输入按照n的大小排序，使得处理答案时的时间复杂度为线性的，不然会TLE

code：

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
          #include
          
            #include
           
             #include
            
              using namespace std; #define INF 0x3f3f3f3f #define PI acos(-1.0) #define mem(a, b) memset(a, b, sizeof(a)) #define mod 1000000007 typedef pair
             
               pii; typedef long long LL; //------------------------------ const int maxn = 100005; //long long f[10000005]; // //void table(){ // f[1] = 1; // long long sum = 2; // for(int i = 2; i <= 10000000; i++){ // f[i] = (f[i-1] * sum) % mod; // sum = sum * (i+1) % mod; // } //} //int n; //int main(){ // table(); // while(scanf("%d",&n) != EOF){ // printf("%d\n",(int)f[n]); // } // return 0; //} //应该离线处理 struct node{ int n, id; bool operator < (const node nt) const{ return n < nt.n; } }ma[maxn]; int cnt = 0; int ans[maxn]; void solve(){ long long sum = 1; long long tmp = 1; int st = 1; for(int i = 0; i < cnt; i++){ for(int j = st; j <= ma[i].n; j++){ tmp = (tmp * sum) % mod; sum = sum * (j+1) % mod; } st = ma[i].n + 1; ans[ma[i].id] = (int)tmp; } for(int i = 0; i < cnt; i++){ printf("%d\n",ans[i]); } } int n; int main(){ cnt = 0; while(scanf("%d",&n) != EOF){ ma[cnt].n = n; ma[cnt].id = cnt++; } sort(ma, ma+cnt); solve(); return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：LeetCode Minimum Size Subarray ..	下一篇：UVA 10271 Chopsticks（线性DP)

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: