hdu 5139 Formula (离线)

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

Source

BestCoder Round #21

推出公式：f [n]=f [n-1] * n!

时间复杂度O(n)，按理说打表可以过的，但是这种题卡内存，直接打表会MLE

所以要进行离线处理，整体输入、整体操作、整体输出

输入完后排个序，确定打表的精准大小

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=1e5+20;

struct node
{
    ll q,ans,id;
}s[N];

bool cmp(node x,node y)
{
    if(x.q!=y.q)
        return x.q<y.q;
}

bool cmp2(node x,node y)
{
    return x.id<y.id;
}

int main()
{
    int tot=0;
    memset(s,0,sizeof(s));
    while(~scanf("%lld",&s[++tot].q))
    {
        s[tot].id=tot;
    }
    tot--;
    sort(s+1,s+tot+1,cmp);
    ll res=1;
    ll tmp=1;
    int cnt=1;
    for(int i=1;i<=s[tot].q;i++)
    {
        tmp=(tmp*i)%mod;
        res=(res*tmp)%mod;
        while(s[cnt].q==i)
        {
            s[cnt].ans=res;
            cnt++;
        }
    }
    sort(s+1,s+tot+1,cmp2);
    for(int i=1;i<=tot;i++)
        cout<<s[i].ans<<'\n';
    return 0;
}