2014
02-12

# 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

#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;
}

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

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