本题直接看很难看出规律,打表可以发现当n为偶数时规律很明显,如下图:
不难看出最后每个ai的系数跟杨辉三角有关,手玩几个样例可以发现当n为4的倍数时最后一列是相减,非4的倍数时最后一列是相加,当n为奇数时可以先算一列转换成偶数来做.
记组合数c(n,m),那么当n为偶数时最后一列的系数每两个数一组依次为c(n/2−1,i/2),直接预处理组合数再根据上述规律算即可
c++
#include<bits/stdc++.h>
由n个整数构成的数组{a1,a2,...,an},我们有如下操作:
你必须在这些整数之间交替写下加减符号,例如假设数组初始值 {1,2,3,4},交替写下加减符号变为1+2−3+4;
此时会生成第二行数组{1+2,2−3,3+4},即{3,−1,7};随后,再次交替写下加减符号变为3−(−1)+7(由于上一行末尾是+,所以这一行的开头是−);
此时会生成第三行数组{4,6},继续重复上述操作;
直到最后只剩下唯一一个数字时,中止操作,在上方的样例中,最后剩下的数字为−2。
现在,你需要独立求出给定的数组剩下的最后一个值是多少。
第一行输入一个整数n(1≤n≤105)代表数组中的元素数量。
第二行输入n个整数a1,a2,...,an (1≤ai≤109)代表数组元素。
在一行上输出一个整数,表示剩下的最后一个值。由于答案可能很大,只需要输出答案对109+7取模的结果。
输入
4
1 2 3 4
输出
1000000005
说明
该样例已在题面中说明,注意,负数也需要取模。