Problem

codeforces

Luogu

Solution

n \leq 200000 通过这个数据告诉我们，我们的算法至差应该为 O(nlogn)

我们就是在计算过程中，你应该会无从下手。

减法啊，那要怎么办呢，如果只是加法就好了啊，你就可以二项式定理上手搞。

我们尝试填充第一二行的符号可以发现：

如果 n 为奇数，那么第二行的第一个符号就和第一行的符号不一样，就是为减号。

如果 n 为偶数，那么第二行的第一个符号应该为加号。

为什么要思考这一些呢，因为我们在寻找一个共性。

然后你把 n=4 的数列出来

这时候可以发现后面有一个化成加法的东西。

于是可以再写一下，你就可以发现规律了

在后面中，第奇数个 a[i]（按照你懂的某种方式）加起来就可以作为最后一次运算左边的那个数，

而偶数个 a[i]（按照你懂的某种方式）加起来就可以作为最后一次运算右边的那个数。

蓝色和蓝色相加可以变成 a_1+2a_3+a_5。

1 2 1

你是否想到什么呢？对，就是二项式定理。

考虑最后的操作符

每一行比上一行多上 i 个，如果多上奇数个，那么就会改变最下面的操作符，而我们加上偶数个却不改变，所以我们可以得到，最后一个操作符应该是按四循环，n%4 可以得到

++--++-- 01230123

我们已经知道了，最后两个数的计算方法

奇数个 a[i] 乘上系数加起来就可以作为最后一次运算左边的那个数， 偶数个 a[i] 乘上系数加起来就可以作为最后一次运算右边的那个数。

所以我们最后一个操作符是什么，那么我们做完最后一次运算就可以得到答案了。

n\%4==0

n\%4==2

那 n 为奇数怎么办呢，我们暴力解决就好了，直接暴力递推到下一行。

Code

#include <bits/stdc++.h>
using namespace std;

#define il inline
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef unsigned long long ull;

il ll qpow(ll a, ll b)
{
    ll res = 1, base = a;
    while (b)
    {
        if (b & 1) res = res * base % MOD;
        base = base * base % MOD;
        b >>= 1;
    }
    return res;
}

#define N 200010

ll fac[N], n, a[N], ans;

ll C(int m, int n)
{
    return fac[n] % MOD * qpow(fac[m], MOD - 2) % MOD * qpow(fac[n - m], MOD - 2) % MOD;
}

int main()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    fac[0] = 1;
    for (int i = 1; i <= n / 2 + 10; i++) fac[i] = (fac[i - 1] * i) % MOD;
    if (n == 1)
    {
        printf("%lld", a[n]);
        return 0;
    }
    if (n % 2 == 1)
    {
        n--;
        for (int i = 1, op = 1; i <= n; i++, op *= -1) a[i] = a[i] + op * a[i + 1];
    }
    for (int i = 1, op = 1; i <= n; i++)
    {
        int qwq = ((i - 1) / 2);
        ans += a[i] * op * C(qwq, (n - 2) / 2);
        ans %= MOD;
        op *= (n % 4 == 2 ? 1 : -1);
    }
    printf("%lld", (ans + MOD) % MOD);

    return 0;
}