首页 > ACM题库 > HDU-杭电 > hdu 2674 N!Again-动态规划-[解题报告]C++
2014
02-12

hdu 2674 N!Again-动态规划-[解题报告]C++

N!Again

问题描述 :

WhereIsHeroFrom:             Zty, what are you doing ?
Zty:                                     I want to calculate N!……
WhereIsHeroFrom:             So easy! How big N is ?
Zty:                                    1 <=N <=1000000000000000000000000000000000000000000000…
WhereIsHeroFrom:             Oh! You must be crazy! Are you Fa Shao?
Zty:                                     No. I haven’s finished my saying. I just said I want to calculate N! mod 2009

Hint : 0! = 1, N! = N*(N-1)!

输入:

Each line will contain one integer N(0 <= N<=10^9). Process to end of file.

输出:

Each line will contain one integer N(0 <= N<=10^9). Process to end of file.

样例输入:

4 
5

样例输出:

24
120

点击打开链接

分析:

本来以为大数,后来才发现要对2009求余,所以一下子就简单了。。。。。。

当n=41时,n!%2009==0。之后的就为0了。

#include"stdio.h"
#include"string.h"
int dp[41];
void fun()
{
	int i;
	dp[0]=1;
	dp[1]=1;
	dp[2]=2;
	for(i=3;i<=40;i++)
		dp[i]=(dp[i-1]*i)%2009;
}

int main()
{
	int n;
	int i,j;
	fun();
	while(scanf("%d",&n)!=-1)
	{
		if(n>40)printf("0\n");
		else printf("%d\n",dp[n]);
	}
	return 0;
}

解题转自:http://blog.csdn.net/yangyafeiac/article/details/8857633


  1. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。

  2. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。