-
- 加为好友
- 发送私信
- 在线聊天
dlyme- 等级:
- 可用分等级：
- 总技术分：
- 总技术分排名：
-
|
| 发表于：2008-08-18 16:52:161楼 得分:0 |
Tom forgot his password! Fortunately he is self-knowledge to write some hints for the password before. But he is too busy to
solve the hints, so he asked you, a good friend of him to help him.
Task
For a given sequence a[1], a[2], ..., a[m], you can find a polynomial whose degree is no more than m-1, f(i) =
a[i],(1 <=i <=m). f(m+1) is the password of Tom. Your task is to find out the password by the given sequence.
Input
There are multiple cases in the input.
There is only one integer on the line 1, indicating the number of the cases.
Each case begins with one integer m (1 <= m <= 200), which is the amount of sequence. Then there are m integers, a[1], a[2],
..., a[m].
Output
For each test, print the password in a single line.
Sample Input
3
3 2 4 6
3 1 4 9
6 1 1 1 1 1 1
Sample output
8
16
1
===============================================================
假设这个多项式为：f(x)=c(m-1)*x^(m-1)+c(m-2)*x^(m-2)+...+c(1)*x+c(0)
该多项式共有m个系数（可以看作m个未知量），又
f(i)=a[i]，1 <=i <=m
带入可得m个方程。解这个线性方程组，就可以确定下来多项式。
由于这个方程组比较特殊(范德蒙行列式)，所以计算起来还算方便。 | | |
修改
删除
举报
引用
回复
| |
