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$.

题意概述

有$n$个正整数$a_i$写在一行。依次对相邻两个数交错进行加减运算，并把结果写在下一行，重复这一过程直到只剩下一个数。第一次进行的是加法运算，求最后得到的数。

数据范围：$1 \le n \le 2 \times 10^5, \ 1 \le a_i \le 10^9$。

算法分析

先列举$n \le 12$的情况：

$$
\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}
$$

可以发现，对于模$4$余$1$的$n$，其答案中第$i \ (i \bmod 2=1)$项的系数为${2n/4 \choose i/2}$；对于模$4$余$2$的$n$也有类似的结论。而对于模$4$余$0$或余$3$的$n$，都可以由$(n-2)$的答案推导出来。

接下来就是计算组合数的问题。易知${n \choose 0}=1, {n \choose i} \times {n-i \over i+1}={n \choose i+1}$。由于涉及到模意义下的除法，因此还需要计算逆元。

代码

#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;
}