程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 5139 (離線處理)

hdu 5139 (離線處理)

編輯:C++入門知識

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;
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved