首页 > 代码库 > HDOJ 5139 Formula 离线

HDOJ 5139 Formula 离线

2024-08-07 06:09:56   214人阅读

找规律
f(1)=1
f(2)=1*1*2=(1)*(1*2)=1!*2!
f(3)=1*1*1*2*2*3=(1)*(1*2)*(1*2*3)=1!*2!*3!

式子可以简化为 f(n)=∏i=1n(n!)%MOD，直接打表不行，会超内存，可以对数据进行离线处理。排好序之后从小到大暴力。ClogC+10000000 ,C为case数目。


Formula
Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 714    Accepted Submission(s): 255


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
 




#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long int LL;
const LL maxn=10001000;
const LL mod=1000000007;

int a,id;

struct QUE
{
	int x,id;
	LL ans;
}que[maxn];

bool cmp1(QUE a,QUE b)
{
	return a.x<b.x;
}

bool cmp2(QUE a,QUE b)
{
	return a.id<b.id;
}

LL now,nowans;
LL nowjiecheng;

LL jiec(LL x)
{
	for(int i=now+1;i<=x;i++)
	{
		nowjiecheng=(nowjiecheng*i)%mod;
	}
	now=x;
	return nowjiecheng;
}

int main()
{
	while(scanf("%d",&a)!=EOF)
	{
		que[id].x=a; que[id].id=id;
		id++;
	}
	sort(que,que+id,cmp1);
	now=1,nowans=1,nowjiecheng=1;
	for(int i=0;i<id;i++)
	{
		if(que[i].x==now)
		{
			que[i].ans=nowans; 
		}
		else if(que[i].x>now)
		{
			LL temp=1;
			for(int j=now+1;j<=que[i].x;j++)
			{
				temp=(temp*jiec(j))%mod;
			}
			nowans=(nowans*temp)%mod;
			que[i].ans=nowans;
		}
	}
	sort(que,que+id,cmp2);
	for(int i=0;i<id;i++)
	{
		cout<<que[i].ans<<endl;
	}
	return 0;
}




HDOJ 5139 Formula 离线






























        

            
                
                  
                
                

                    联系

                    我们