# Karen and Test

## 题目描述

Karen has just arrived at school, and she has a math test today!
The test is about basic addition and subtraction. Unfortunately, the teachers were too busy writing tasks for Codeforces rounds, and had no time to make an actual test. So, they just put one question in the test that is worth all the points.
There are $n$ integers written on a row. Karen must alternately add and subtract each pair of adjacent integers, and write down the sums or differences on the next row. She must repeat this process on the values on the next row, and so on, until only one integer remains. The first operation should be addition.
Note that, if she ended the previous row by adding the integers, she should start the next row by subtracting, and vice versa.
The teachers will simply look at the last integer, and then if it is correct, Karen gets a perfect score, otherwise, she gets a zero for the test.
Karen has studied well for this test, but she is scared that she might make a mistake somewhere and it will cause her final answer to be wrong. If the process is followed, what number can she expect to be written on the last row?
Since this number can be quite large, output only the non-negative remainder after dividing it by $10^9+7$.

## 算法分析

\begin{align} n=1,\;&ans=a_1 \\ n=2,\;&ans=a_1+a_2 \\ n=3,\;&ans=a_1+2a_2-a_3 \\ n=4,\;&ans=a_1-a_2+a_3-a_4 \\ n=5,\;&ans=a_1+2a_3+a_5 \\ n=6,\;&ans=a_1+a_2+2a_3+2a_4+a_5+a_6 \\ n=7,\;&ans=a_1+2a_2+a_3+4a_4-a_5+2a_6-a_7 \\ n=8,\;&ans=a_1-a_2+3a_3-3a_4+3a_5-3a_6+a_7-a_8 \\ n=9,\;&ans=a_1+4a_3+6a_5+4a_7+a_9 \\ n=10,\;&ans=a_1+a_2+4a_3+4a_4+6a_5+6a_6+4a_7+4a_8+a_9+a_{10} \\ n=11,\;&ans=a_1+2a_2+3a_3+8a_4+2a_5+12a_6-2a_7+8a_8-3a_9+2a_{10}-a_{11} \\ n=12,\;&ans=a_1-a_2+5a_3-5a_4+10a_5-10a_6+10a_7-10a_8+5a_9-5a_{10}+a_{11}-a_{12} \end{align}

## 代码

#include <iostream>
#define MOD 1000000007
using namespace std;
long long n, t, r[3], ans, c[200001], a[200001];
void extend_gcd(long long a, long long b, long long &x, long long &y) {
if (!b) {
x = 1, y = 0;
return;
}
extend_gcd(b, a % b, y, x);
y -= a / b * x;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
t = (n - 1) / 4 << 1;
c[0] = 1;
for (int i = 0; i < t; ++i) {
long long x, y;
extend_gcd(i + 1, MOD, x, y);
c[i + 1] = c[i] * (t - i) % MOD * x % MOD;
if (c[i + 1] < 0) c[i + 1] += MOD;
}
for (int i = 0; i <= t; ++i) {
r[0] += c[i] * a[(i << 1) + 1] % MOD;
if (!(n & 1)) r[0] += c[i] * a[(i << 1) + 2] % MOD;
}
r[0] %= MOD;
if ((n - 1) % 4 < 2) cout << r[0] << endl;
else {
for (int i = 0; i <= t; ++i) {
r[1] += c[i] * a[(i << 1) + 2] % MOD;
if (!(n & 1)) r[1] -= c[i] * a[(i << 1) + 3] % MOD;
}
r[1] %= MOD;
for (int i = 0; i <= t; ++i) {
r[2] += c[i] * a[(i << 1) + 3] % MOD;
if (!(n & 1)) r[2] += c[i] * a[(i << 1) + 4] % MOD;
}
r[2] %= MOD;
if (n & 1) ans = (r[0] + (r[1] << 1) - r[2]) % MOD;
else ans = (r[0] - (r[1] << 1) - r[2]) % MOD;
if (ans < 0) ans += MOD;
cout << ans << endl;
}
return 0;
}


418 I'm a teapot