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

题目链接

题目描述

一个正整数序列 $a_1, a_2, \dots, a_n$ 被称为 前缀平方序列，如果其所有前缀和 $S_k = \sum_{i=1}^k a_i$ 都是完全平方数。给定两个正整数 $n$ 和 $m$ ，请计算满足以下条件的前缀平方序列的数量：

序列长度为 $n$ 。
总和 $S_n \le m$ 。

结果需要对 $1,000,000,007$ 取模。

输入:

一行输入两个整数 $n, m$ 。

输出:

输出一个整数，表示满足条件的序列数量模 $1,000,000,007$ 的值。

解题思路

这道题表面上是关于序列计数，但可以通过分析其内在结构，将其转化为一个经典的组合数学问题。

首先，我们来分析“前缀平方序列”的性质。设序列的前缀和为 $S_1, S_2, \dots, S_n$ 。根据题意，每个 $S_k$ 都必须是一个完全平方数。我们可以设 $S_k = x_k^2$ ，其中 $x_k$ 是一个正整数。

$S_1 = a_1 = x_1^2$
$S_2 = a_1 + a_2 = x_2^2$
...
$S_k = S_{k-1} + a_k = x_k^2$

由于序列 $a$ 中的每个元素 $a_k$ 都必须是正整数，我们可以得到： $a_k = S_k - S_{k-1} = x_k^2 - x_{k-1}^2 > 0$ (对于 $k > 1$ ) $a_1 = S_1 = x_1^2 > 0$

从 $x_k^2 - x_{k-1}^2 > 0$ 可以推导出 $x_k^2 > x_{k-1}^2$ 。因为 $x_k$ 都是正数，所以 $x_k > x_{k-1}$ 。同时， $x_1 > 0$ 。这样，我们就建立了一个从序列 $a$ 到序列 $x$ 的一一对应关系。原问题等价于寻找一个满足特定条件的整数序列 $x_1, x_2, \dots, x_n$ 。

这个序列 $x$ 需要满足以下条件：

$0 < x_1 < x_2 < \dots < x_n$ ，即一个长度为 $n$ 的严格递增正整数序列。
$S_n = x_n^2 \le m$ ，这意味着 $x_n \le \sqrt{m}$ 。

所以，问题被转化为了：从集合 $\{1, 2, 3, \dots, \lfloor\sqrt{m}\rfloor\}$ 中，选出 $n$ 个不同的数，能组成多少个严格递增的序列？

一旦我们从这个集合中选定了 $n$ 个不同的数，它们自动就只能以一种方式（从小到大）排列成一个满足条件的严格递增序列 $x_1, \dots, x_n$ 。因此，问题的核心就变成了从 $K = \lfloor\sqrt{m}\rfloor$ 个数中选出 $n$ 个数的组合数。

答案就是组合数 $\binom{K}{n}$ 。

如果 $n > K$ ，则无法选出 $n$ 个不同的数，方案数为 0。否则，我们需要计算 $\binom{K}{n} \pmod{1000000007}$ 。由于模数是质数，我们可以使用公式： $\binom{K}{n} = \frac{K!}{n!(K-n)!} = \frac{\prod_{i=0}^{n-1}(K-i)}{n!} \pmod{P}$ 我们可以先计算分子 $\prod_{i=0}^{n-1}(K-i)$ ，再计算分母 $n!$ ，然后用费马小定理求出分母的模逆元，最后相乘得到结果。

具体的计算步骤：

计算 $K = \lfloor\sqrt{m}\rfloor$ 。
如果 $n > K$ ，答案为 0。
否则，计算分子 num = (K) * (K-1) * ... * (K-n+1) mod P。
计算分母 den = n! mod P。
使用快速幂计算 den 的模逆元 inv_den = power(den, P-2, P)。
最终答案为 (num * inv_den) mod P。

代码

cpp
java
python

#include <iostream>
#include <cmath>

using namespace std;
using LL = long long;

const int MOD = 1e9 + 7;

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 inverse(LL n) {
    return power(n, MOD - 2);
}

LL combinations(LL k, LL n) {
    if (n > k) return 0;
    if (n == 0 || n == k) return 1;
    if (n > k / 2) n = k - n;

    LL numerator = 1;
    for (LL i = 0; i < n; ++i) {
        numerator = (numerator * (k - i)) % MOD;
    }

    LL denominator = 1;
    for (LL i = 1; i <= n; ++i) {
        denominator = (denominator * i) % MOD;
    }

    return (numerator * inverse(denominator)) % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    LL n, m;
    cin >> n >> m;

    LL k = sqrt(m);
    
    cout << combinations(k, n) << '\n';

    return 0;
}

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

public class Main {
    static final int MOD = 1_000_000_007;

    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 inverse(long n) {
        return power(n, MOD - 2);
    }

    static long combinations(long k, long n) {
        if (n < 0 || n > k) {
            return 0;
        }
        if (n == 0 || n == k) {
            return 1;
        }
        if (n > k / 2) {
            n = k - n;
        }

        long numerator = 1;
        for (long i = 0; i < n; i++) {
            numerator = (numerator * (k - i)) % MOD;
        }

        long denominator = 1;
        for (long i = 1; i <= n; i++) {
            denominator = (denominator * i) % MOD;
        }

        return (numerator * inverse(denominator)) % MOD;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long m = sc.nextLong();

        long k = (long) Math.sqrt(m);

        System.out.println(combinations(k, n));
    }
}

import math

MOD = 1_000_000_007

def combinations(k, n, mod):
    if n < 0 or n > k:
        return 0
    if n == 0 or n == k:
        return 1
    if n > k // 2:
        n = k - n
    
    numerator = 1
    for i in range(n):
        numerator = (numerator * (k - i)) % mod
    
    denominator = 1
    for i in range(1, n + 1):
        denominator = (denominator * i) % mod
    
    return (numerator * pow(denominator, mod - 2, mod)) % mod

n, m = map(int, input().split())

k = int(math.sqrt(m))

print(combinations(k, n, MOD))

算法及复杂度

算法：数学、组合计数
时间复杂度： $\mathcal{O}(n + \log(\text{MOD}))$ 。计算组合数需要 $O(n)$ 的循环，求模逆元需要 $O(\log(\text{MOD}))$ 的快速幂。由于 $n \le \lfloor\sqrt{m}\rfloor \approx 31622$ ，此复杂度足够高效。
空间复杂度： $\mathcal{O}(1)$ 。