Formula

f(n)=(∏i=1nin−i+1)%1000000007
You are expected to write a program to calculate f(n) when a certain n is given.

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

  
  

   
   2
100
  
  

  
  

   
   2
148277692
  
  

题意：计算i从1~n的i^（n-i-1）的乘积。

普通打表 超内存+超时，，，

不妨将所有的输入数据都存进一个结构体中一个是no（表示输入时的顺序）一个是num（表示输入的数据n），再按照num的大小排序，之后依次找与num相等的数，并将其的值赋给out中

没想到还可以这样。。学习了

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL __int64
using namespace std;
const LL M = 100005;
const LL mod = 1000000007;

struct node{
	LL no, num;
}s[M];
LL out[M];

int cmp(node a, node b){
	return a.num < b.num;
}

int main(){
	LL n, cnt = 0;
	while(scanf("%I64d", &n) == 1){
		s[cnt].no = cnt;
		s[cnt].num = n;
		cnt++;
	}
	LL a, b, index = 0, i;
	sort(s, s+cnt, cmp);
	a = 1; b = 1;
	for(i = 1; index != cnt; i ++){
		a = (a*i)%mod;
		b = (b*a)%mod;
		while(index !=cnt &&s[index].num == i){
			out[s[index++].no] = b;
		}
	}
	for(i = 0; i < cnt; i ++){
		printf("%I64dn", out[i]);
	}
	return 0;
}

最后

以上就是寒冷大碗为你收集整理的Bestcoder #21&&hdoj 5139 Formula 【另类打表之分块】Formula的全部内容，希望文章能够帮你解决Bestcoder #21&&hdoj 5139 Formula 【另类打表之分块】Formula所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。