题解 | #交替加减#

题目链接

题目描述

给定一个由 $n$ 个整数构成的数组，进行如下操作：

在数组元素之间交替插入 + 和 - 号（第一个是 +），形成一个表达式并计算，得到一个新数组。
对新数组重复此过程，但这次插入的符号序列的起始符号，与上一轮符号序列的末尾符号相反。
重复以上步骤，直到数组只剩下一个数字。

求这个最终剩下的数字对 $10^9+7$ 取模的结果。

解题思路

直接模拟 $n-1$ 轮操作的复杂度为 $O(n^2)$ ，无法通过本题。我们需要找到最终结果与初始数组之间的数学关系。最终结果可以表示为初始数组元素的线性组合： $Result = \sum_{i=0}^{n-1} c_i \cdot a_i$ 。我们的目标是求出系数 $c_i$ 。

通过对不同 $n$ 的推导，可以发现系数 $c_i$ 的规律与组合数有关，并且具体形式取决于 $n \pmod 4$ 的值。

当 $n$ 是偶数时 ( $n=2k$ )：
- 最终结果可以表示为 $\sum_{j=0}^{k-1} C_{k-1}^{j} \cdot (a_{2j} \text{ op } a_{2j+1})$ 。
- 操作符 $\text{op}$ 取决于 $k$ 的奇偶性：
  - 若 $k$ 是偶数 (即 $n \pmod 4 = 0$ )，则 $\text{op}$ 为 $-$ 。
  - 若 $k$ 是奇数 (即 $n \pmod 4 = 2$ )，则 $\text{op}$ 为 $+$ 。
当 $n$ 是奇数时 ( $n=2k+1$ ):
- 若 $k$ 是偶数 (即 $n \pmod 4 = 1$ )，最终结果为 $\sum_{j=0}^{k} C_{k}^{j} \cdot a_{2j}$ 。只有偶数下标的元素有贡献。
- 若 $k$ 是奇数 (即 $n \pmod 4 = 3$ )，规律变得复杂。例如 $n=3$ 时结果为 $a_0 + 2a_1 - a_2$ 。在这种情况下，我们可以通过将 $n$ 减一，并对数组进行一次变换，然后套用偶数情况的逻辑来求解。具体地，我们将数组 $a$ 变换为 $a'$ ，其中 $a'_i = a_i + (-1)^i \cdot a_{i+1}$ ，然后对 $n-1$ 个元素的 $a'$ 数组求解。由于 $n-1$ 必为偶数，且新一轮计算的起始符号为 $+$ ，这会引导至 $(n-1) \pmod 4 = 2$ 的情况。

算法步骤：

根据 $n \pmod 4$ 的值，选择对应的计算公式。
预计算组合数所需的阶乘和阶乘逆元。
根据公式，遍历数组 $a$ ，将每个元素乘以其对应的系数，累加求和。
所有计算都在模 $10^9+7$ 下进行，注意处理负数取模。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;
using LL = long long;

const int MOD = 1e9 + 7;

// 快速幂求a^b mod p
LL 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;
}

// 费马小定理求逆元
LL inv(LL n) {
    return power(n, MOD - 2);
}

// 预处理阶乘和阶乘逆元
vector<LL> fact, invFact;
void precompute_factorials(int n) {
    if (n < 0) return;
    fact.resize(n + 1);
    invFact.resize(n + 1);
    fact[0] = 1;
    invFact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
        invFact[i] = inv(fact[i]);
    }
}

// 使用预处理的阶乘和逆元计算组合数
LL nCr_mod_p(int n, int r) {
    if (r < 0 || r > n) return 0;
    return (((fact[n] * invFact[r]) % MOD) * invFact[n - r]) % MOD;
}

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

    int n;
    cin >> n;
    vector<LL> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // n=1 是边界情况，直接输出
    if (n == 1) {
        cout << (a[0] % MOD + MOD) % MOD << "\n";
        return 0;
    }

    // 当 n % 4 == 3 时，进行一次变换，转化为 n % 4 == 2 的情况
    if (n % 4 == 3) {
        vector<LL> next_a(n - 1);
        for (int i = 0; i < n - 1; ++i) {
            if (i % 2 == 0) {
                next_a[i] = (a[i] + a[i+1]);
            } else {
                next_a[i] = (a[i] - a[i+1]);
            }
        }
        a = next_a;
        n--;
    }

    LL ans = 0;
    // n % 4 == 1 的情况
    if (n % 2 == 1) {
        int k = (n - 1) / 2;
        precompute_factorials(k);
        for (int j = 0; j <= k; ++j) {
            LL C = nCr_mod_p(k, j);
            ans = (ans + (C * a[2 * j]) % MOD) % MOD;
        }
    } else { // n 为偶数的情况
        int k = n / 2;
        precompute_factorials(k - 1);
        if (k % 2 == 1) { // n % 4 == 2 的情况
            for (int j = 0; j < k; ++j) {
                LL C = nCr_mod_p(k - 1, j);
                LL term = (a[2 * j] + a[2 * j + 1]);
                ans = (ans + (C * (term % MOD + MOD) % MOD)) % MOD;
            }
        } else { // n % 4 == 0 的情况
            for (int j = 0; j < k; ++j) {
                LL C = nCr_mod_p(k - 1, j);
                LL term = (a[2 * j] - a[2 * j + 1]);
                ans = (ans + (C * (term % MOD + MOD) % MOD)) % MOD;
            }
        }
    }

    cout << (ans + MOD) % MOD << "\n";

    return 0;
}

import java.util.Scanner;

public class Main {
    static final int MOD = 1_000_000_007;
    static long[] fact;
    static long[] invFact;

    // 快速幂求a^b mod p
    static long power(long base, long exp) {
        long res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }

    // 费马小定理求逆元
    static long inv(long n) {
        return power(n, MOD - 2);
    }

    // 预处理阶乘和阶乘逆元
    static void precomputeFactorials(int n) {
        if (n < 0) return;
        fact = new long[n + 1];
        invFact = new long[n + 1];
        fact[0] = 1;
        invFact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = (fact[i - 1] * i) % MOD;
            invFact[i] = inv(fact[i]);
        }
    }

    // 使用预处理的阶乘和逆元计算组合数
    static long nCr_mod_p(int n, int r) {
        if (r < 0 || r > n) return 0;
        return (((fact[n] * invFact[r]) % MOD) * invFact[n - r]) % MOD;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }

        // n=1 是边界情况，直接输出
        if (n == 1) {
            System.out.println((a[0] % MOD + MOD) % MOD);
            return;
        }

        // 当 n % 4 == 3 时，进行一次变换，转化为 n % 4 == 2 的情况
        if (n % 4 == 3) {
            long[] next_a = new long[n - 1];
            for (int i = 0; i < n - 1; i++) {
                if (i % 2 == 0) {
                    next_a[i] = a[i] + a[i+1];
                } else {
                    next_a[i] = a[i] - a[i+1];
                }
            }
            a = next_a;
            n--;
        }

        long ans = 0;
        // n % 4 == 1 的情况
        if (n % 2 == 1) {
            int k = (n - 1) / 2;
            precomputeFactorials(k);
            for (int j = 0; j <= k; ++j) {
                long C = nCr_mod_p(k, j);
                ans = (ans + (C * a[2 * j]) % MOD) % MOD;
            }
        } else { // n 为偶数的情况
            int k = n / 2;
            precomputeFactorials(k - 1);
            if (k % 2 == 1) { // n % 4 == 2 的情况
                 for (int j = 0; j < k; ++j) {
                    long C = nCr_mod_p(k - 1, j);
                    long term = (a[2 * j] + a[2 * j + 1]);
                    long term_mod = (term % MOD + MOD) % MOD;
                    ans = (ans + (C * term_mod) % MOD) % MOD;
                }
            } else { // n % 4 == 0 的情况
                for (int j = 0; j < k; ++j) {
                    long C = nCr_mod_p(k - 1, j);
                    long term = (a[2 * j] - a[2 * j + 1]);
                    long term_mod = (term % MOD + MOD) % MOD;
                    ans = (ans + (C * term_mod) % MOD) % MOD;
                }
            }
        }

        System.out.println((ans + MOD) % MOD);
    }
}

MOD = 10**9 + 7

# 预计算阶乘和阶乘逆元
MAX_N = 200000 # 根据题目n的最大范围设定
fact = [1] * (MAX_N + 1)
invFact = [1] * (MAX_N + 1)
for i in range(1, MAX_N + 1):
    fact[i] = (fact[i-1] * i) % MOD

# 使用费马小定理和递推计算阶乘逆元
invFact[MAX_N] = pow(fact[MAX_N], MOD - 2, MOD)
for i in range(MAX_N - 1, -1, -1):
    invFact[i] = (invFact[i+1] * (i+1)) % MOD

# 使用预处理的阶乘和逆元计算组合数
def nCr_mod_p(n, r):
    if r < 0 or r > n:
        return 0
    numerator = fact[n]
    denominator = (invFact[r] * invFact[n - r]) % MOD
    return (numerator * denominator) % MOD

def main():
    n = int(input())
    a = list(map(int, input().split()))

    # n=1 是边界情况，直接输出
    if n == 1:
        print((a[0] % MOD + MOD) % MOD)
        return

    # 当 n % 4 == 3 时，进行一次变换，转化为 n % 4 == 2 的情况
    if n % 4 == 3:
        next_a = [0] * (n - 1)
        for i in range(n - 1):
            if i % 2 == 0:
                next_a[i] = a[i] + a[i+1]
            else:
                next_a[i] = a[i] - a[i+1]
        a = next_a
        n -= 1
    
    ans = 0
    # n % 4 == 1 的情况
    if n % 2 == 1:
        k = (n - 1) // 2
        for j in range(k + 1):
            C = nCr_mod_p(k, j)
            ans = (ans + C * a[2 * j]) % MOD
    else: # n 为偶数的情况
        k = n // 2
        if k % 2 == 1: # n % 4 == 2 的情况
            for j in range(k):
                C = nCr_mod_p(k - 1, j)
                term = a[2 * j] + a[2 * j + 1]
                ans = (ans + C * term) % MOD
        else: # n % 4 == 0 的情况
            for j in range(k):
                C = nCr_mod_p(k - 1, j)
                term = a[2 * j] - a[2 * j + 1]
                ans = (ans + C * term) % MOD

    # 最终结果处理负数取模
    print((ans + MOD) % MOD)

if __name__ == "__main__":
    main()

算法及复杂度

算法：数学、组合计数、分类讨论
时间复杂度： $O(N)$ 。所有情况都只需要遍历一次数组，而组合数查询在 $O(N)$ 预处理后为 $O(1)$ 。
空间复杂度： $O(N)$ ，用于存储阶乘和阶乘逆元数组。