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]);

    }

}

巴特西

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

Formula

最新文章

热门文章