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

题目链接

前缀平方和序列

题目描述

设一个正整数序列 $a_1, a_2, \dots, a_n$ 的前缀和为 $S_i = \sum_{j=1}^{i} a_j$ 。若对于所有的 $i \in [1, n]$ ， $S_i$ 都是完全平方数，则称该序列为一条前缀平方序列。

给定两个正整数 $n$ 与 $m$ ，请你计算满足以下两个条件的前缀平方序列的数量：

序列长度为 $n$ 。
对任意前缀和 $S_i$ 均有 $S_i \le m$ 。

结果对 $10^9+7$ 取模。

解题思路

这是一个计数问题，我们可以通过分析前缀平方序列的结构，将其转化为一个经典的组合数学问题。

1. 结构分析

根据定义，序列 $a_1, a_2, \dots, a_n$ 的前缀和 $S_1, S_2, \dots, S_n$ 都是完全平方数。

我们可以设 $S_i = k_i^2$ ，其中 $k_i$ 是一个正整数。

$S_1 = a_1 = k_1^2$
$S_2 = a_1 + a_2 = k_2^2$
...
$S_n = a_1 + a_2 + \dots + a_n = k_n^2$

由于序列中的 $a_i$ 都是正整数，所以对于任意 $i > 1$ ，都有 $a_i = S_i - S_{i-1} > 0$ 。

这意味着 $S_i > S_{i-1}$ 。

代入我们设定的变量，即 $k_i^2 > k_{i-1}^2$ 。因为 $k_i$ 都是正整数，所以这等价于 $k_i > k_{i-1}$ 。

由此，我们得到一个关键结论：序列 $k_1, k_2, \dots, k_n$ 是一个严格单调递增的正整数序列。

即 $0 < k_1 < k_2 < \dots < k_n$ 。

2. 约束转化

题目给出的另一个约束是 $S_i \le m$ 对所有 $i$ 都成立。

由于 $S_i$ 是一个递增序列，这个约束等价于其最大项 $S_n \le m$ 。

即 $k_n^2 \le m$ ，这等价于 $k_n \le \lfloor\sqrt{m}\rfloor$ 。

3. 问题重构

现在，原问题被转化为了： 计算有多少个长度为 $n$ 的严格递增正整数序列 $k_1, k_2, \dots, k_n$ ，其最大项 $k_n$ 不超过 $\lfloor\sqrt{m}\rfloor$ 。

这个问题可以进一步简化。我们只需要从整数集合 $\{1, 2, \dots, \lfloor\sqrt{m}\rfloor\}$ 中选出 $n$ 个不同的数。一旦选定了这 $n$ 个数，只有一种方式可以将它们排列成一个严格递增的序列（即从小到大排列）。

因此，问题的核心就是：从 $\lfloor\sqrt{m}\rfloor$ 个数中选出 $n$ 个数的组合数。

令 $limit = \lfloor\sqrt{m}\rfloor$ ，则答案为 $\binom{limit}{n}$ 。

4. 组合数计算

我们需要计算 $\binom{limit}{n} \pmod{10^9+7}$ 。

组合数公式为 $\binom{a}{b} = \frac{a!}{b! \cdot (a-b)!}$ 。

在模运算下，除法需要用乘法逆元来计算。因为模数 $10^9+7$ 是一个质数，我们可以使用费马小定理来求逆元，即 $x^{p-2} \equiv x^{-1} \pmod p$ 。

计算步骤如下：

计算 $limit = \lfloor\sqrt{m}\rfloor$ 。
如果 $limit < n$ ，则无法选出 $n$ 个数，方案数为 $0$ 。
预处理阶乘及其逆元。由于 $n$ 的范围可达 $10^5$ ，而 $limit$ 最大约为 $\sqrt{10^9} \approx 31622$ ，我们需要预处理到 $10^5$ 。
利用公式 $\binom{a}{b} \equiv a! \cdot (b!)^{-1} \cdot ((a-b)!)^{-1} \pmod p$ 计算结果。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

const int MOD = 1000000007;
const int MAX_N = 100001;

// 用于存储阶乘和阶乘的逆元
vector<long long> fact(MAX_N);
vector<long long> invFact(MAX_N);

// 快速幂函数，用于计算 x^y % mod
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 模块化逆元函数
long long modInverse(long long n) {
    return power(n, MOD - 2);
}

// 预计算阶乘和阶乘的逆元
void precompute() {
    fact[0] = 1;
    invFact[0] = 1;
    for (int i = 1; i < MAX_N; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
        invFact[i] = modInverse(fact[i]);
    }
}

// 组合数计算函数
long 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;
}

int main() {
    precompute();
    long long n, m;
    cin >> n >> m;
    
    long long limit = static_cast<long long>(sqrt(m));
    
    cout << nCr_mod_p(limit, n) << endl;
    
    return 0;
}

import java.util.Scanner;
import java.lang.Math;

public class Main {
    static final int MOD = 1000000007;
    static final int MAX_N = 100001;
    static long[] fact = new long[MAX_N];
    static long[] invFact = new long[MAX_N];

    // 快速幂函数
    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 modInverse(long n) {
        return power(n, MOD - 2);
    }

    // 预计算阶乘和阶乘的逆元
    static void precompute() {
        fact[0] = 1;
        invFact[0] = 1;
        for (int i = 1; i < MAX_N; i++) {
            fact[i] = (fact[i - 1] * i) % MOD;
            invFact[i] = modInverse(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) {
        precompute();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long m = sc.nextLong();
        
        long limit = (long) Math.sqrt(m);
        
        System.out.println(nCr_mod_p((int) limit, n));
    }
}

import math

MOD = 1000000007
MAX_N = 100001

# 预计算阶乘和阶乘的逆元
fact = [1] * MAX_N
invFact = [1] * MAX_N

for i in range(1, MAX_N):
    fact[i] = (fact[i - 1] * i) % MOD

invFact[MAX_N - 1] = pow(fact[MAX_N - 1], MOD - 2, MOD)
for i in range(MAX_N - 2, -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

# 读取输入
n, m = map(int, input().split())

limit = int(math.sqrt(m))

# 计算并输出结果
print(nCr_mod_p(limit, n))

算法及复杂度

算法：数论、组合数学
时间复杂度：预处理阶乘和逆元的时间复杂度为 $\mathcal{O}(N \log P)$ （若每次单独求逆元）或 $\mathcal{O}(N)$ （若线性求逆元），其中 $N$ 是预处理的范围（ $10^5$ ）， $P$ 是模数。查询阶段，sqrt 和组合数计算都是 $\mathcal{O}(1)$ 。总时间复杂度由预处理主导，为 $\mathcal{O}(N)$ 。
空间复杂度：需要两个数组存储阶乘和逆元，大小为 $N$ 。因此，总空间复杂度为 $\mathcal{O}(N)$ 。