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;
}

 

 

全部评论

相关推荐

06-12 17:46
门头沟学院 Java
运营你豪哥:来说重点: ​1.项目前置,时间倒序。​​ 2.​项目描述强化结果与量化效果(STAR原则里的R)。​​ ​3.个人技能精炼,明确掌握程度,突出核心。​​ ​4.增加强有力开头的个人总结部分。​​ 5.​优化教育背景(成绩排名)、合并奖项与活动。​​
听劝,我这个简历该怎么改...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务