首页 > ACM题库 > HDU-杭电 > hdu 3445 The Diary of Math Teacher待解决[解题报告]C++
2014
03-23

hdu 3445 The Diary of Math Teacher待解决[解题报告]C++

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.

输出:

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.

样例输入:

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

样例输出:

38
3
4
0
748
4035


Hint
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


  1. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。

  2. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧