程式師世界 >> 編程語言 >> 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;
}