形式化题目

给定一个长度为 $n$ 的数组 $A$。每一秒钟，数组会通过变换变成长度减少 $1$ 的新数组 $A'$，变换规则如下：

1. 如果当前数组 $A$ 的长度 $n$ 为偶数，则 $A'[i] = A[i] + A[i+1]$（$1 \le i < n$）。
2. 如果当前数组 $A$ 的长度 $n$ 为奇数，则 $A'[i] = A[i] - A[i+1]$（$1 \le i < n$）。

经过 $n-1$ 秒后，数组只剩下一个数字。求该数字对 $10^9+7$ 取模后的结果。

数据范围

• 对于 40% 的数据，满足 $n \le 1000$。
• 对于 100% 的数据，满足 $1 \le n \le 10^5$，$1 \le A_i \le 10^9$。

其他约束

• 题面未给出具体的时空限制，常规可假设为 1000ms / 128MB（config.json 的 "memory": 128）。
• 输入为单组数据。第一行为 $n$，接下来一行为 $n$ 个整数。

正解

思路

朴素的做法是直接模拟上述过程，因为每次操作长度减 $1$，总共进行 $n-1$ 次操作，每次操作需要遍历数组，所以总时间复杂度为 $O(n^2)$，可以拿到 $40\%$ 的分数。 由于 $n \le 10^5$，我们要寻找更低复杂度的算法。

本题可以通过多项式和位移算子 $E$（满足 $E A_i = A_{i+1}$）来简化操作：

• 长度为偶数时的操作（$A[i]+A[i+1]$）相当于对原数组乘上多项式 $1+E$。
• 长度为奇数时的操作（$A[i]-A[i+1]$）相当于对原数组乘上多项式 $1-E$。

最后数组剩下的唯一一个元素，相当于把原数组 $A$ 作用了一系列多项式的乘积 $P(E)$ 后取其首项，即为 $\sum_{j=0}^{n-1} c_j A_{j+1}$，其中 $c_j$ 是多项式 $P(x)$ 中 $x^j$ 的系数。

我们分析 $P(x)$ 的规律。由于数组长度从 $n$ 逐渐递减到 $2$，奇偶性交替出现：

• 如果 $n$ 是奇数（设 $n = 2k + 1$）： 操作的多项式依次为 $(1-x)$，$(1+x)$，$(1-x)$，$(1+x)$ … 并以 $(1+x)$ 结尾。 总共有 $2k$ 步，恰好包含了 $k$ 次 $(1-x)$ 和 $k$ 次 $(1+x)$。 所以 $P(x) = ( (1-x)(1+x) )^k = (1-x^2)^k$。 将式子二项式展开，非零项只能是偶数次项 $x^{2p}$，其系数为 $(-1)^p \binom{k}{p}$。奇数次项系数则为 $0$。

• 如果 $n$ 是偶数（设 $n = 2k$）： 操作的多项式依次为 $(1+x)$，$(1-x)$，$(1+x)$ … 并以 $(1+x)$ 结尾。 总共有 $2k-1$ 步，包含了 $k$ 次 $(1+x)$ 和 $k-1$ 次 $(1-x)$。 所以 $P(x) = ( (1+x)(1-x) )^{k-1} \cdot (1+x) = (1-x^2)^{k-1} (1+x)$。 展开后可以看出，$x^{2p}$ 和 $x^{2p+1}$ 拥有相同的系数，均为 $(-1)^p \binom{k-1}{p}$。

利用上述公式，我们可以很轻松地通过组合数直接求出 $A$ 数组中每个元素最终在答案中的系数。提前 $O(n)$ 预处理阶乘以及逆元后，就能在 $O(n)$ 时间内算出最终答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-10 08:04
# update_at: 2026-10-10 08:42

import sys

MOD = 1_000_000_007
type FactList = list[int]  # 组合数预处理数组，下标 i 存 i! 或其逆元


def build_combinations(n: int) -> tuple[FactList, FactList]:
    """预处理阶乘与阶乘逆元，用来 O(1) 求组合数。"""
    fact = [1] * (n + 1)
    inv_fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i % MOD
    inv_fact[n] = pow(fact[n], MOD - 2, MOD)
    for i in range(n - 1, -1, -1):
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD
    return fact, inv_fact


def coefficient(n: int, pos: int, fact: FactList, inv_fact: FactList) -> int:
    """第 pos 个数（从 1 开始）在最终答案中的系数：C(⌈n/2⌉-1, ⌈pos/2⌉-1) 带 (−1)^(⌈pos/2⌉-1)。"""
    if n % 2 == 1 and pos % 2 == 0:
        return 0  # n 为奇数时 (1−x²)^k 只有偶次项，奇数下标全为 0
    half_pos = (pos + 1) // 2
    half_n = (n + 1) // 2
    choose = fact[half_n - 1] * inv_fact[half_pos - 1] % MOD * inv_fact[half_n - half_pos] % MOD
    return -choose if half_pos % 2 == 0 else choose


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    try:
        n = next(data)
    except StopIteration:
        return

    fact, inv_fact = build_combinations(n)
    values = [next(data) for _ in range(n)]
    answer = sum(value * coefficient(n, pos, fact, inv_fact)
                 for pos, value in enumerate(values, 1)) % MOD
    print(answer)


if __name__ == "__main__":
    solve()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 08:04
 * update_at: 2026-10-10 08:40
 */
#include <iostream>
using namespace std;

typedef long long ll;

const ll MOD = 1000000007LL;
const int MAXN = 200000 + 5;

ll fact[MAXN];     // fact[i] = i! mod MOD
ll inv_fact[MAXN]; // inv_fact[i] = (i!)^{-1} mod MOD

ll quick_power(ll base, ll exp) {
    ll res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) {
            res = res * base % MOD;
        }
        base = base * base % MOD;
        exp /= 2;
    }
    return res;
}

void init_comb(int n) {
    fact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }
    inv_fact[n] = quick_power(fact[n], MOD - 2);
    for (int i = n - 1; i >= 0; i--) {
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;
    }
}

ll comb(int n, int m) {
    if (m < 0 || m > n) {
        return 0;
    }
    return fact[n] * inv_fact[m] % MOD * inv_fact[n - m] % MOD;
}

// 第 pos 个数（从 1 开始）在最终答案中的系数。
ll coefficient(int n, int pos) {
    if ((n % 2 == 1) && (pos % 2 == 0)) {
        return 0;
    }
    int half_pos = (pos + 1) / 2;
    int half_n = (n + 1) / 2;
    ll c = comb(half_n - 1, half_pos - 1);
    if (half_pos % 2 == 0) {
        return -c;
    }
    return c;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) {
        return 0;
    }

    init_comb(n);

    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ll a = 0; // 预置 0：输入被截断时不读未初始化值
        cin >> a;
        ans = (ans + (a % MOD) * coefficient(n, i)) % MOD;
    }

    cout << (ans + MOD) % MOD << '\n';
    return 0;
}

复杂度

• 时间复杂度：$O(n)$。预处理阶乘及其逆元需要 $O(n)$ 的时间（加上一次求逆元的 $O(\log MOD)$），随后遍历计算每个元素的系数并累加同样耗时 $O(n)$，总体时间复杂度 $O(n)$。
• 空间复杂度：$O(n)$。需要大小为 $O(n)$ 的数组来存储原数据序列，以及预处理的阶乘与逆元。

总结

• 这是一道经典地利用位移算子和多项式，把多轮交替的差分与相邻求和问题转化为组合数求解的题目。
• 解题关键是敏锐地发现多项式相乘后引发的奇偶消项效应：$(1-x)(1+x) = 1-x^2$。
• 代码实现细节：由于计算过程中系数有可能为负数，在 C++ 计算中应当正确处理对取模的影响，常采用 (val % MOD + MOD) % MOD。

验证

验证记录（R2，与官方 std.cpp 三方对拍）

⚠ 本题无本地 data/（data.json 的 files=[]）⇒ check_new_analysis 报 「无 data/（跳过）」= 空转（T1/T65）。证据来源是官方 std.cpp（★★★★）。

结论

main.cpp ≡ std.cpp ≡ main.py，在全部六类证据上 0 分歧 ⇒ 与官方 std.cpp 三方一致 （★ 不能写成「验证通过」）。

★ T67 语义核对（第一优先级）—— 对专家描述的订正

结论：专家的「多项式乘法 (1-x)(1+x)=1-x²」属实，但表述不完整。

std.cpp（42 行）不是逐轮模拟，而是闭式组合公式：对第 i 项（1-based）返回

代码为 cal()：if(n&1 && !(m&1)) return 0; → m=(m+1)/2; n=(n+1)/2; now=comb(n-1,m-1); m%2==0 ? -now : now。

六类证据（T14 分级）

V1 反事实表（300 组真进程对比 std）

★ 探针有效性：4 个变体各失败 146–300 次 ⇒ 「0 失败」的 V1d/V1e 是真 no-op， 不是探针失效（T35 判据鉴别力）。

V9 UBSan + 对照组 · T38

• ★ 对照组（强制 INT_MIN 取反）确实报错 negation of -2147483648 cannot be represented… ⇒ 探针有效；main.cpp UBSan 跑多组（含 n=99999 全 1e9、n=1e5 随机）stderr 全空，-ftrapv rc=0
• config.json：time=1000ms / memory=128MB。实测 main 0.01s / 8.4MB、 std 0.08s / 8.4MB、main.py 0.05s / 34MB ⇒ 全部通过，内存 ≥3.7× 余量

与 std.cpp 的逐行差异点（7 条，均不影响语义）

本次对 index.md 的两处修正（worker 提出，父会话机械核实后执行）

1. ★ 「其他约束」原写 1000ms / **256MB**，而 config.json 是 "memory": **128** ⇒ 已改为 128MB（机械核实：grep '"memory"' config.json → 128）
2. ★ 原「验证」节称「数据文件与官方 std 的推断结论完全一致」 —— 本题无本地 data/，该句无证据支撑（T65）⇒ 已删除该表述， 改为「与官方 std.cpp 在 388 组合成数据上三方一致（无本地 data/）」