题解 | #前缀平方和序列#

问题分析

该问题的核心在于对“前缀平方序列”定义的转化。给定长度为 $n$ 的正整数序列 $a_1, a_2, \dots, a_n$ ，其前缀和定义为 $s_i = \sum_{j=1}^i a_j$ 。题目要求 $s_i$ 必须满足以下三个约束条件：

平方数约束：每个 $s_i$ 必须是一个完全平方数。
正整数约束：由于 $a_i \ge 1$ ，前缀和序列必须是严格单调递增的，即 $1 \le s_1 < s_2 < \dots < s_n$ 。
上界约束：所有前缀和不得超过 $x$ ，即 $s_n \le x$ 。

令 $s_i = k_i^2$ ，其中 $k_i$ 为正整数。基于上述约束，我们可以将问题转化为关于平方根序列 $k_1, k_2, \dots, k_n$ 的计数问题：

由 $s_i = k_i^2$ 且 $s_i < s_{i+1}$ 可知， $k_i^2 < k_{i+1}^2$ 。由于 $k_i$ 是正整数，这等价于 $k_i < k_{i+1}$ 。
由 $s_i \le x$ 可知， $k_i^2 \le x$ ，即 $k_i \le \lfloor \sqrt{x} \rfloor$ 。

因此，原问题等价于：从集合 $\{1, 2, 3, \dots, \lfloor \sqrt{x} \rfloor\}$ 中选择 $n$ 个互不相同的正整数，并将它们按升序排列形成序列 $(k_1, k_2, \dots, k_n)$ 的方案数。

组合数学

由于序列 $k_i$ 一旦选定且必须保持严格递增，那么对于任何选出的 $n$ 个元素的集合，其排列方式是唯一的。因此，该问题本质上是一个经典的组合问题。

计算可选范围：计算可用的最大平方根 $M = \lfloor \sqrt{x} \rfloor$ 。这是序列中任何元素对应的平方根能取到的最大整数值。
数学建模：方案数等于从 $M$ 个元素中选取 $n$ 个元素的组合数，即 $C(M, n)$ 或记作 $\binom{M}{n}$ 。
边界处理：若 $n > M$ ，根据鸽巢原理，无法构造长度为 $n$ 的严格递增序列，结果直接为 0。
计算模型选择：由于 $n, M \le 1000$ ，且需要对 $10^9 + 7$ 取模，有两种主流选型：
- 动态规划（杨辉三角）：利用 $C(i, j) = C(i-1, j-1) + C(i-1, j) \pmod P$ 预计算。
- 乘法逆元：利用公式 $\frac{M!}{n!(M-n)!} \pmod P$ 计算。在此规模下，动态规划不仅实现简单，且能完全避免处理逆元时的开销。

复杂度分析

时间复杂度：

计算 $M$ ： $O(\log x)$ 或 $O(1)$ （取决于 sqrt 实现）。
计算组合数（DP）：需要填充一个 $M \times n$ 的矩阵，复杂度为 $O(M \cdot n)$ 。
总复杂度： $O(M \cdot n)$ 。

空间复杂度：

状态存储：需要 $O(M \cdot n)$ 的矩阵存储组合数结果。
优化空间：如果采用滚动数组，空间可以压缩至 $O(n)$ 。

代码实现

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

static constexpr int MOD = 1e9 + 7;

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

    int n, x;
    cin >> n >> x;
    int M = sqrt(x);

    if (n > M) {
        cout << 0 << endl;
        return 0;
    }

    vector<vector<int>> dp(M + 1, vector<int>(n + 1, 0));
    for (int i = 0; i <= M; i++) {
        dp[i][0] = 1;
    }

    for (int i = 0; i <= M; i++) {
        for (int j = 1; j <= min(i, n); j++) {
            dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % MOD;
        }
    }

    cout << dp[M][n] << endl;
}