http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1088. 差分计算
时间限制:1.0s   内存限制:512.0MB  
总提交次数:861   AC次数:613   平均分:74.77
将本题分享到:
   
 
问题描述
  我们经常玩一个游戏:给定序列的前四个数是1,4,9,16,问序列的下一个数是多少?
  对于这个问题,通常是要找到一个多项式f (x),使f (1)为序列的第一个数, f (2)为序列的第二个数,依此类推。比如可以找到一个多项式f (x) = x2满足上面的性质,那么我们认为下一个数就是f (5) = 25。这种多项式有多个,一般我们希望找到最高次幂最小的那个。
  要找到这样的多项式并不容易,下面介绍一种差分的方法来玩这样游戏:
  1. 设置一个累加和s,初始为0。设给出的序列为(a1, a2, …, an)
  2. 将an加到s中,将序列变为(a2-a1, a3-a2, …, anan-1)
  3. 重复2,直到序列变为空。
  上述过程结束后,s中保存的就是所求的下一个数。

  例如,对于序列(1, 4, 9, 16),游戏的过程如下:
  1. s = 0;
  2. 将16加到s中,s = 16,序列变为(3, 5, 7);
  3. 将7加到s中,s = 23,序列变为(2, 2);
  4. 将2加到s中,s = 25,序列变为(0);
  5. 将0加到s中,s = 25,序列变为();
  6. 现在序列为空,结束,所求的数为25。
输入格式
  输入的第一行包含一个整数n,表示给定的序列的长度,n<=30。
  第二行有n个整数,表示初始的序列。保证按上面的方法计算中间结果不超过int的范围。
样例输入
4
1 4 9 16
样例输出
25
样例输出
4
1 2 4 8
样例输出
15