主页 讨论版 问题 名次 状态 统计
欢迎加入西电微软俱乐部招新群 588166170,做出福利题,免技术部第一次面试且赠送“福利”海报或小礼品~~~~
问题 B: Godv的数列

问题 B: Godv的数列

时间限制: 3 Sec  内存限制: 128 MB
提交: 272  解决: 31
[提交][状态][讨论版]

题目描述

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取模后输出

输入

多组数据,第一行为数据组数T1<=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

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