【CUGBACM15级BC第21场 B】Formula

Formula

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

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

 

由于N非常大，直接打表会MLE；
应该就数据进行离线处理，就是先把数据存起来，然后集中处理数据；
输入完数据后排序O（ClogC）；
然后再暴力O(N)；
总的时间复杂度O(ClogC+N);
还好不会超时；

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <cassert>
#define inf 0x3f3f3f3f
#define eps 1e-5
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
#define N  100010
#define mod 1000000007
using namespace std;

struct node
{
    int number, order, ans;
} a[N];
int cmp(node a, node b)
{
    return a.number < b.number;
}
int cmp2(node a, node b)
{
    return a.order < b.order;
}
int main()
{
    int n, i, num = 0, k;
    while (~scanf("%d", &n))
    {
        a[num].number = n;
        a[num].order = num;
        num++;
    }
    sort(a, a + num, cmp);
    long long answer = 1, pre = 1, pren = 1;
    for (i = 1, k = 0; i <= a[num - 1].number; i++)
    {
        pren = (pren * i) % mod;
        answer = (pre * pren) % mod;
        pre = answer;
        while (a[k].number == i) ///重复元素消除
        {
            a[k].ans = answer;
            k++;
        }
    }
    
    sort(a, a + num, cmp2);
    for (i = 0; i < num; i++)
    {
        printf("%d\n", a[i].ans);
    }
    return 0;
}