hdu 5139(离线处理+离散化下标)

Formula

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1204    Accepted Submission(s): 415

Problem Description

f(n)=(∏i=1nin−i+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]
1≤n≤10000000

Output

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

Sample Input

2
100

Sample Output

2
148277692

题解:F[n] = 1ⁿ*2^n-1*3^n-2...*n ,这里的 F[n] 是可以通过一层循环就求解出来的,但是还是会超时。只能够将所有的询问保存下来,然后排个序,但是数字太大明显不能够作为下标,开个结构体记录下标,然后离散化下标,最后找到下标依次输出。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include <queue>
using namespace std;
typedef long long LL;
const LL mod = ;
struct Ask
{
    LL v;
    int ori;
} ask[];
LL a[];
int cmp(Ask a,Ask b){
    return a.v<b.v;
}
int main()
{
    int n,id=;
    ask[].v = ask[].ori = ;
    while(scanf("%d",&n)!=EOF)
    {
        ask[id].v = n;
        ask[id].ori = id;
        id++;
    }
    sort(ask+,ask+id,cmp);
    for(int i=;i<id;i++){
        a[ask[i].ori] = i;
    }
    LL cnt = ,ans=;
    for(int i=; i<id; i++)
    {
        for(int j=ask[i-].v+; j<=ask[i].v; j++)
        {
            cnt = cnt*j%mod;
            ans = ans*cnt%mod;
        }
        a[ask[i].ori] = ans;
    }
    for(int i=;i<id;i++){
        printf("%lld\n",a[i]);
    }
}