题目描述

给定正整数 $N$ 和 $K$。定义一个长度为 $N+1$ 的序列 $A = (A_0, A_1, \dots, A_N)$ 如下：
对于 $0 \le i < K$，$A_i = 1$。
对于 $K \le i$，$A_i = A_{i-K} + A_{i-K+1} + \dots + A_{i-1}$。

要求计算 $A_N$ 的值，结果对 $10^9$ 取模。

样例

输入:
4 2

输出:
5

说明：
$A_0 = 1, A_1 = 1$
$A_2 = A_0 + A_1 = 1 + 1 = 2$
$A_3 = A_1 + A_2 = 1 + 2 = 3$
$A_4 = A_2 + A_3 = 2 + 3 = 5$
所以 $A_4 = 5$。

输入:
10 20

输出:
1

说明：
$N=10, K=20$。因为 $N < K$，所以 $A_N$ 属于初始条件定义的范围。$A_{10} = 1$。

输入:
1000000 500000

输出:
420890625

注意结果要对 $10^9$ 取模。

算法 (递推 + 滑动窗口优化)

$O(N)$

思路分析

1. 理解递推关系:
   序列 $A$ 的定义是一个线性递推关系。对于 $i \ge K$， $A_i$ 是其前面 $K$ 项的和。
   $$A_i = \sum_{j=i-K}^{i-1} A_j$$

2. 朴素计算:
   我们可以直接按照定义计算序列 $A$ 的每一项，直到 $A_N$。

   • 初始化 $A_0, A_1, \dots, A_{K-1}$ 为 1。
   • 对于 $i$ 从 $K$ 到 $N$，计算 $A_i = (A_{i-K} + \dots + A_{i-1}) \pmod{10^9}$。
     计算每一项 $A_i$ 都需要求和 $K$ 个数。如果 $N$ 和 $K$ 都很大，那么总时间复杂度将是 $O(N \times K)$。根据数据范围 $N, K \le 10^6$， $N \times K$ 可能高达 $10^{12}$，这在 2 秒的时间限制内是无法接受的。因此，我们需要优化计算过程。

3. 优化：滑动窗口求和:
   观察计算 $A_i$ 和 $A_{i+1}$ 的过程：
   $$A_i = A_{i-K} + A_{i-K+1} + \dots + A_{i-1}$$
   $$A_{i+1} = A_{i-K+1} + A_{i-K+2} + \dots + A_{i-1} + A_i$$
   我们发现 $A_{i+1}$ 的求和项与 $A_i$ 的求和项有大量的重叠。具体地：
   $$A_{i+1} = (A_{i-K} + A_{i-K+1} + \dots + A_{i-1}) - A_{i-K} + A_i$$
   $$A_{i+1} = A_i - A_{i-K} + A_i$$
   $$A_{i+1} = 2A_i - A_{i-K}$$
   这个关系好像不对，我们直接维护和本身。
   令 $S_i = \sum_{j=i-K}^{i-1} A_j$。那么根据定义 $A_i = S_i$ (对于 $i \ge K$)。
   我们想计算 $A_{i+1}$，即 $S_{i+1} = \sum_{j=i-K+1}^{i} A_j$。
   观察 $S_i$ 和 $S_{i+1}$ 的关系：
   $$S_{i+1} = A_{i-K+1} + \dots + A_{i-1} + A_i$$
   $$S_i = A_{i-K} + A_{i-K+1} + \dots + A_{i-1}$$
   因此， $S_{i+1} = S_i - A_{i-K} + A_i$。
   这意味着，如果我们维护一个变量 s，表示当前计算 $A_i$ 时所需的和（即 $S_i = \sum_{j=i-K}^{i-1} A_j$），那么计算出 $A_i = s$ 之后，我们可以用 $O(1)$ 的时间更新这个和，得到 $S_{i+1}$，用于计算下一项 $A_{i+1}$。更新规则是：s_new = s_old - A[i-K] + A[i] (所有运算在模 $10^9$ 下进行)。

4. 算法流程:

   • 设置模数 $P = 10^9$。
   • 创建一个数组 a （或 vector） 大小为 $N+1$，用于存储序列 $A$ 的值。
   • 初始化前 $K$ 项：a[0] = a[1] = ... = a[K-1] = 1。
   • 初始化滑动窗口的和 s：s = a[0] + ... + a[K-1] = K (模 $P$)。
   • 从 $i = K$ 循环到 $N$：
     a. 计算当前项：a[i] = s。
     b. 更新滑动窗口的和 s，为计算下一项 a[i+1] 做准备：
     * 减去窗口最左边的项：s = s - a[i - K]。
     * 加上新计算出的项：s = s + a[i]。
     * 注意处理模运算，特别是减法可能导致负数。需要确保结果在 $[0, P-1]$ 范围内。例如 s = (s % P + P) % P。如果使用支持模运算的类（如代码中的 ModInt），则可以自动处理。
   • 循环结束后，a[N] 就是所求的答案。

5. 代码实现细节:

   • 代码使用了模板类 ModInt<P>，其中 P = 1000000000，来封装模运算。这使得代码更简洁，不易出错。Z 是 ModInt<P> 的别名。
   • vector<Z> a(n + 1, 1); 初始化了一个大小为 n + 1 的 ModInt 向量，并将所有元素初始化为 1。这正好满足了 $A_0$ 到 $A_{K-1}$ (甚至更多项) 等于 1 的初始条件。
   • Z s = k; 初始化滑动窗口的和。因为前 $K$ 项都是 1，它们的和就是 $K$。
   • 循环 for (int i = k; i <= n; i ++ ) 实现了从第 $K$ 项开始的递推计算。
   • a[i] = s; 计算 $A_i$。
   • s = s - a[i - k] + a[i]; 更新滑动窗口的和。ModInt 类自动处理了加法、减法以及取模操作。
   • 最后输出 a[n]。

时间复杂度

• 初始化数组和求和变量：$O(N)$ 或 $O(K)$。
• 主循环从 $K$ 到 $N$，共 $N-K+1$ 次迭代。
• 每次迭代内部的操作（赋值、加法、减法）都是 $O(1)$ 的（模运算视为常数时间）。
• 总时间复杂度为 $O(N)$。这对于 $N \le 10^6$ 是完全可以接受的。

空间复杂度

• 需要存储序列 $A$ 直到第 $N$ 项，空间复杂度为 $O(N)$。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

using namespace std;
using i64 = long long; // 定义 i64 为 long long 的别名
using u64 = unsigned long long; // 定义 u64
using u32 = unsigned; // 定义 u32
// using u128 = unsigned __int128; // 定义 u128 (本题未使用)

// 快速幂模板 (ModInt 类内部会调用或类似实现)
template<class T>
constexpr T power(T a, u64 b, T res = 1) {
    for (; b != 0; b /= 2, a *= a) {
        if (b & 1) {
            res *= a;
        }
    }
    return res;
}

// 模乘模板 (ModInt 类内部会调用或类似实现)
template<u32 P>
constexpr u32 mulMod(u32 a, u32 b) {
    return u64(a) * b % P;
}
template<u64 P>
constexpr u64 mulMod(u64 a, u64 b) {
    // 使用 Barrett reduction 或其他优化，这里是一种实现方式
    u64 res = a * b - u64(1.L * a * b / P - 0.5L) * P;
    res %= P;
    return res;
}

// 安全取模，处理负数
constexpr i64 safeMod(i64 x, i64 m) {
    x %= m;
    if (x < 0) {
        x += m;
    }
    return x;
}

// 扩展欧几里得算法求逆元 (ModInt 类内部会调用或类似实现)
constexpr std::pair<i64, i64> invGcd(i64 a, i64 b) {
    a = safeMod(a, b);
    if (a == 0) {
        return {b, 0};
    }
    i64 s = b, t = a;
    i64 m0 = 0, m1 = 1;
    while (t) {
        i64 u = s / t;
        s -= t * u;
        m0 -= m1 * u;
        std::swap(s, t);
        std::swap(m0, m1);
    }
    if (m0 < 0) {
        m0 += b / s;
    }
    return {s, m0};
}

// 模整数模板类定义 (ModIntBase)
// ... [省略 ModIntBase, Barrett, DynModInt 的完整定义，它们提供了基础的模运算支持] ...

// 定义本题使用的模数 P
constexpr int P = 1000000000;
// 使用 ModInt 模板，定义类型别名 Z
using Z = ModInt<P>;

// 主函数
int main() {
    // 关闭同步，加速 IO
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k; // 输入 N 和 K
    cin >> n >> k;

    // 初始化滑动窗口的和 s。前 K 项都是 1，所以和是 K。
    Z s = k; 
    // 创建大小为 n+1 的向量 a，并初始化所有元素为 1。
    // 这自动处理了 a[0]...a[k-1] = 1 的情况。
    vector<Z> a(n + 1, 1);

    // 从 i = k 开始计算递推项，直到 i = n
    for (int i = k; i <= n; i ++ ) {
        // a[i] 等于前 k 项的和，即当前的窗口和 s
        a[i] = s;
        // 更新窗口和 s，为计算 a[i+1] 做准备
        // 新的和 = 旧的和 - 移出窗口的项 a[i-k] + 新加入窗口的项 a[i]
        s = s - a[i - k] + a[i]; 
        // ModInt 类自动处理模 P 运算
    }

    // 输出最终结果 a[n]
    cout << a[n] << "\n";

    return 0; // 程序正常结束
}