3445：The Diary of Math Teacher

题目描述

03/21/2010 SUN Sunny

“Hi, boys and girls ,today we will learn the “Deference” .”
“What is the “Deference”? Is that difficult? ”
“Boys , don’t worry, and you will know it immediately.”

“f(x) is an function, and x is an integer. Δf( x ) = f (x + 1 ) – f( x ) ”
“In general, Δ(n+1)f( x ) = Δ(n)f( x+1 ) - Δ(n)f( x )”
“In particular, Δ(0)f( x ) = f( x )，Δ(1)f( x ) = Δf (x )”

“Do you understand?”
“No!!!!!!!!!!!!”
“Does anyone understand?”
“Only you our teacher!”
“How dare you be so ironic. Since you all have learnt the Factorial. I will give you a problem of factorial and difference. Anyone who can’t solve it will be severely punished”

“ The problem is:
Given a nonnegative integer array {a[n]} , and each of its elements a[i] (1<=i<=n)is also known.
f(x)=∏{1<=i<=n}(x+a[i])
Your task is to calculate Δ(k)f(0)/k! ”
Damn it,really bad mood. Well, I'd better go to sleep now.

输入解释

Multiple test cases.
The first line of each test case will be 3 integers : n(1<=n<=1000) , k(0<=k<=n-1) , p(1<=P<=20000).
The following line will contain n integers a[i] (0<=a[i]<=20000).
Input ends with n=k=p=0.

输出解释

For each test case ,pint the answer mod p in one separate line.
The last case n=k=p=0 does not need to be processed.

输入样例

5 3 20000
1 0 0 1 0
5 3 7
1 0 1 0 0
3 1 7777
1 1 0
3 0 94
0 1 1
7 4 10000
0 1 0 3 0 1 0
16 12 17595
4898 287 4879 598 5927 8 764 57 233 188 58 97 899 9876 47 323
0 0 0

输出样例

提示

In the first test case:
f( x ) = ∏{1<=i<=5}(x + a[i]) = (x + a[1])(x + a[2])(x + a[3])(x + a[4])(x + a[5]) = (x + 1)*x*x*(x + 1)*x

So , f(0) = 0 , f(1) = 4 , f(2) = 72 , f(3) = 432
Δf(0) = 4 , Δf(1) = 68 , Δf(2) = 360
Δ(2)f(0) = 64 , Δ(2)f(1) = 292
Δ(3)f(0) = 228
3! = 1*2*3 = 6
228/6 = 38

来自杭电HDUOJ的附加信息

Recommend

zhouzeyong

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 2010 ACM-ICPC Multi-University Training Contest（2）——Host by BUPT

源链接： HDU-3445

最后修改于 2020-10-25T23:03:39+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
2000/1000MS(Java/Others)	32768/32768K(Java/Others)