首页 > 代码库 > HDU 5139 Formula 卡内存

HDU 5139 Formula 卡内存

题目就是求这个

n达到10^7,测试数据组数为10^5

 

为了防止TLE,一开始把每个n对应的值先求出来,但发现竟然开不了10^7的数组(MLE),然后就意识到这是第一道卡内存的题目。。。

只能离线做,把每个n从小到大排序,然后从小到大依次求,然后把结果存下来,最后排回去输出。

 

#include<cstdio>#include<cstring>#include<cmath>#include<iostream>#include<algorithm>#include<set>#include<map>#include<stack>#include<vector>#include<queue>#include<string>#include<sstream>#define eps 1e-9#define ALL(x) x.begin(),x.end()#define INS(x) inserter(x,x.begin())#define FOR(i,j,k) for(int i=j;i<=k;i++)#define MAXN 100005#define MAXM 10000005#define INF 0x3fffffff#define MOD 1000000007using namespace std;typedef long long LL;struct node{	int num,i,ans;};int i,n,size,maxn,p;node G[MAXN];bool flag;bool cmp(node x,node y){	return x.num<y.num;}bool cmp2(node x,node y){	return x.i<y.i;}int main(){	while (~scanf("%d",&n))	{		G[size].num=n;		G[size].i=size;		size++;	}	sort(G,G+size,cmp);	LL mul=1;	LL last=0;	LL d=1;	for (p=0;p<size;p++)	{		for (i=last+1;i<=G[p].num;i++)		{			mul=(mul*i)%MOD;			d=(d*mul)%MOD;		}		G[p].ans=d;		last=G[p].num;	}	sort(G,G+size,cmp2);	for (i=0;i<size;i++)	{		printf("%d\n",G[i].ans);	}	return 0;}

  

 

HDU 5139 Formula 卡内存