「一个人的高三楼」题解

题目大意

给定一个长度为 $n$ 的数列，要求计算它的 $k$ 次前缀和。即：

• 第 $1$ 次前缀和：$S_i^{(1)} = \sum_{j=1}^i a_j$
• 第 $2$ 次前缀和：$S_i^{(2)} = \sum_{j=1}^i S_j^{(1)}$
• ...
• 第 $k$ 次前缀和：$S_i^{(k)} = \sum_{j=1}^i S_j^{(k-1)}$

解题思路

关键观察

$k$ 次前缀和可以通过组合数来计算：

$$S_i^{(k)} = \sum_{j=0}^i \binom{k-1+i-j}{k-1} a_j$$

这个公式的推导基于：

• 每次前缀和操作相当于与序列 $[1,1,1,\dots]$ 做卷积
• $k$ 次前缀和相当于与序列 $\left[\binom{k-1}{k-1}, \binom{k}{k-1}, \binom{k+1}{k-1}, \dots\right]$ 做卷积

算法核心

使用**快速数论变换（NTT）**来加速卷积计算：

1. 构造组合数序列：

   $$b_i = \binom{k-1+i}{k-1} = \frac{(k-1+i)(k-2+i)\cdots(k)}{i!} $$

2. 卷积计算：

   $$S^{(k)} = a * b$$

3. NTT优化：使用NTT将卷积的复杂度从 $O(n^2)$ 降到 $O(n\log n)$

代码解析

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1 << 18 | 8, mod = 998244353;

int n, k, lim, len, a[N], b[N], r[N];

// 快速幂
inline int qpow(int a, int b = mod - 2) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod, b >>= 1;
    }
    return res;
}

// 快速数论变换
void ntt(int *a, int op) {
    // 位逆序置换
    for (int i = 0; i < lim; i++)
        if (i < r[i]) swap(a[i], a[r[i]]);
    
    // 蝴蝶操作
    for (int i = 1; i < lim; i <<= 1) {
        int wn = qpow(3, (mod - 1) / i / 2);
        if (op == -1) wn = qpow(wn);
        
        for (int j = 0; j < lim; j += i << 1)
            for (int k = j, w = 1; k < j + i; k++, w = w * wn % mod) {
                int t = w * a[k + i] % mod;
                a[k + i] = (a[k] - t + mod) % mod;
                a[k] = (a[k] + t) % mod;
            }
    }
    
    // 逆变换时的归一化
    if (op == -1) {
        int inv = qpow(lim);
        for (int i = 0; i < lim; i++)
            a[i] = a[i] * inv % mod;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];
    
    // 构造组合数序列 b[i] = C(k-1+i, k-1)
    b[0] = 1;
    for (int i = 1; i < n; i++) {
        // 递推计算组合数：C(k-1+i, k-1) = C(k-2+i, k-1) * (k-1+i) / i
        b[i] = (k - 1 + i) % mod * b[i - 1] % mod * qpow(i) % mod;
    }
    
    // 初始化NTT参数
    lim = 1, len = 0;
    while (lim < n * 2 - 1) lim <<= 1, len++;
    for (int i = 0; i < lim; i++)
        r[i] = ((r[i >> 1] >> 1) | ((i & 1) << (len - 1)));
    
    // NTT计算卷积
    ntt(a, 1);  // a的正变换
    ntt(b, 1);  // b的正变换
    
    // 点值相乘
    for (int i = 0; i < lim; i++)
        a[i] = a[i] * b[i] % mod;
    
    // 逆变换得到结果
    ntt(a, -1);
    
    // 输出前n项
    for (int i = 0; i < n; i++)
        cout << a[i] << "\n";
    
    return 0;
}

算法正确性

组合数公式推导

$k$ 次前缀和的生成函数表示为：

$$F^{(k)}(x) = \frac{F(x)}{(1-x)^k}$$

展开后得到：

$$S_i^{(k)} = \sum_{j=0}^i \binom{k-1+i-j}{k-1} a_j$$

递推计算组合数

使用递推关系：

$$\binom{k-1+i}{k-1} = \binom{k-2+i}{k-1} \times \frac{k-1+i}{i} $$

避免了直接计算大数阶乘。

复杂度分析

• 时间复杂度：$O(n\log n)$
  • 组合数预处理：$O(n)$
  • 三次NTT：$O(n\log n)$
• 空间复杂度：$O(n)$

样例验证

样例1

输入：4 1
      1 2 3 4
输出：1 3 6 10

验证：一次前缀和正确。

样例2

输入：4 3
      1 2 3 4
输出：1 5 15 35

验证：

• 一次前缀和：[1,3,6,10]
• 二次前缀和：[1,4,10,20]
• 三次前缀和：[1,5,15,35] ✓

总结

本题的解法体现了：

1. 生成函数技巧：将前缀和问题转化为多项式运算
2. 组合数学应用：利用组合数表示重复卷积
3. NTT优化：处理大规模卷积计算
4. 模运算处理：正确处理大数取模

这种结合组合数学和多项式技术的思路，对于解决类似的序列变换问题具有很好的参考价值。