首页 > 代码库 > hdu 5139 Formula (找规律+离线处理)

hdu 5139 Formula (找规律+离线处理)

2024-08-06 14:09:05   221人阅读

Formula

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


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
2100
 

 

Sample Output
2148277692
 
 题目并不难，主要是当时没想到离线处理，以前做题时没用过。把所有数据读入，然后按大小排序，算出答案后，再按照原来顺利输出就行了。

 

#include<stdio.h>#include<math.h>#include<string.h>#include<stdlib.h>#include<vector>#include<algorithm>using namespace std;#define N 1000005#define ll __int64const int mod=1000000007;struct node{    int x,id,s;}a[N];bool cmp1(node a,node b){    return a.x<b.x;}bool cmp2(node a,node b){    return a.id<b.id;}int main(){    int m=0,i,j,n;    ll s,s2,s3;    while(~scanf("%d",&n))    {        a[m].id=m;        a[m++].x=n;    }    sort(a,a+m,cmp1);    s2=s3=1;    s=1;    for(i=0,j=2; i<m; i++)    {        for(; j<=a[i].x; j++)        {            s=s*j;            if(s>=mod)                s%=mod;            s2=(s*s2)%mod;            s3=s2;        }        a[i].s=s2;    }    sort(a,a+m,cmp2);    for(i=0;i<m;i++)        printf("%d\n",a[i].s);    return 0;}

　　

 

hdu 5139 Formula (找规律+离线处理)


联系
我们