问题 1227. -- Godv的数列

1227: Godv的数列

时间限制:1000 ms 内存限制:128 MB
提交:347 解决:38
[ 提交][ 状态][ 讨论版]

题目描述

Godv拿到了一个长度为n(1<=n<=1e5)的数列，数列中每个数ai都满足1<=ai<=1e9。
然后神奇的Godv对这个数列施加了魔法。“巴拉拉能量~~~~哈！~~”
数列在Godv的魔法的影响下，发生了如下的变化：
首先，对相邻数字两两相加，得到一个长为n-1的新数列a’，用伪代码表示如下
for i=1:n-1
a'[i]=a[i]+a[i+1]
用a'代替a
重复进行这样的操作，直到数列长度为1
现在聪明的Godv想考考你，最后剩下的数的大小是多少？由于Godv不喜欢大数，所以请将结果对1001取模后输出

输入

多组数据，第一行为数据组数T（1<=T<=25）。每组数据第一行包含一个数n。第二行为这个数列，每两个数之间用空格隔开

输出

每组数据输出一个数，即最后剩下的数。

样例输入

2 1 1 2 1 2

样例输出

1 3

提示

假设 n=3，初始数列为1 2 3

那么一次变化后，数列变成 3 5 （1+2=3，2+3=5）

再变一次后，变成8 （3+5=8）

ans=8%1001=8

来源

RedClothes

[ 提交][ 状态][ 讨论版]
Baidu
map