题解 | #Y型树#_牛客博客

这个题目的官解比较抽象，我会对其做一个解释。实际上题目所求为p(N-1,3)下文以M代表N-1。这个p(n,k)即代表分拆数 https://oi-wiki.org/math/combinatorics/partition/#%E7%94%9F%E6%88%90%E5%87%BD%E6%95%B0 这个题解里面的公式我让gemini解释了一下来源，很复杂。来尝试从递推关系 $p(n, k) = p(n-1, k-1) + p(n-k, k)$ 和 $p(n, 2) = \lfloor n/2 \rfloor$ (对于 $n \ge 2$ ) 来推导官方代码中使用的 $p(m, 3)$ 公式。

我们有递推关系： $p(m, 3) = p(m-1, 2) + p(m-3, 3)$ 对于 $m \ge 3$ . 已知 $p(m-1, 2) = \lfloor (m-1)/2 \rfloor$ 对于 $m-1 \ge 2$ ，即 $m \ge 3$ . 所以，对于 $m \ge 3$ ，我们有： $p(m, 3) = \lfloor (m-1)/2 \rfloor + p(m-3, 3)$ .

我们可以展开这个递推关系： $p(m, 3) = \lfloor (m-1)/2 \rfloor + p(m-3, 3)$ $p(m, 3) = \lfloor (m-1)/2 \rfloor + \lfloor (m-3-1)/2 \rfloor + p(m-6, 3)$ $p(m, 3) = \lfloor (m-1)/2 \rfloor + \lfloor (m-4)/2 \rfloor + \lfloor (m-6-1)/2 \rfloor + p(m-9, 3)$ $p(m, 3) = \lfloor (m-1)/2 \rfloor + \lfloor (m-4)/2 \rfloor + \lfloor (m-7)/2 \rfloor + p(m-9, 3)$ ...

我们一直展开，直到 $p(\cdot, 3)$ 的参数小于 3。 $p(0, 3) = p(1, 3) = p(2, 3) = 0$ . 设 $m = 3q + r$ , 其中 $r \in \{0, 1, 2\}$ . 展开 $q$ 次后，我们得到： $p(m, 3) = \sum_{j=0}^{q-1} \lfloor (m - 3j - 1)/2 \rfloor + p(m - 3q, 3)$ $p(m, 3) = \sum_{j=0}^{q-1} \lfloor (m - 3j - 1)/2 \rfloor + p(r, 3)$ . 由于 $p(r, 3) = 0$ 对于 $r \in \{0, 1, 2\}$ ，我们有： $p(m, 3) = \sum_{j=0}^{q-1} \lfloor (m - 3j - 1)/2 \rfloor$ , 其中 $q = \lfloor m/3 \rfloor$ . 注意：这个公式对于 $m \ge 3$ 成立。当 $m=0, 1, 2$ 时， $q=0$ ，求和范围是空的，结果是 0，也正确。

所以，我们现在需要证明： $\sum_{j=0}^{\lfloor m/3 \rfloor - 1} \lfloor (m - 3j - 1)/2 \rfloor = \lfloor (m-1)^2/4 \rfloor - \lfloor (m-\lfloor m/3 \rfloor-1)^2/4 \rfloor - \frac{\lfloor m/3 \rfloor (\lfloor m/3 \rfloor+1)}{2} + \lfloor m/3 \rfloor$ .

令 $K = \lfloor m/3 \rfloor$ . 我们需要证明： $\sum_{j=0}^{K-1} \lfloor (m - 3j - 1)/2 \rfloor = \lfloor (m-1)^2/4 \rfloor - \lfloor (m-K-1)^2/4 \rfloor - \frac{K(K+1)}{2} + K$ .

我们知道一个重要的恒等式： $\sum_{i=1}^n \lfloor i/2 \rfloor = \lfloor n^2/4 \rfloor$ . 利用这个恒等式，我们可以写出： $\lfloor (m-1)^2/4 \rfloor = \sum_{i=1}^{m-1} \lfloor i/2 \rfloor$ . $\lfloor (m-K-1)^2/4 \rfloor = \sum_{i=1}^{m-K-1} \lfloor i/2 \rfloor$ . 所以， $\lfloor (m-1)^2/4 \rfloor - \lfloor (m-K-1)^2/4 \rfloor = \sum_{i=m-K}^{m-1} \lfloor i/2 \rfloor$ .

将这个代入要证明的等式右边：右边 $= \sum_{i=m-K}^{m-1} \lfloor i/2 \rfloor - \frac{K(K+1)}{2} + K$ .

所以，问题转化为证明： $\sum_{j=0}^{K-1} \lfloor (m - 3j - 1)/2 \rfloor = \sum_{i=m-K}^{m-1} \lfloor i/2 \rfloor - \frac{K(K+1)}{2} + K$ .

这是一个关于带有步长的求和与连续求和之间的恒等式。这类恒等式通常比较难直接从基本代数推导。它们可能来源于更高级的组合恒等式、生成函数的性质，或者通过对特定类型的求和进行巧妙的变换。

例如，考虑恒等式 $\lfloor x \rfloor = x - \{x\}$ 。左边 $= \sum_{j=0}^{K-1} \left( \frac{m - 3j - 1}{2} - \left\{\frac{m - 3j - 1}{2}\right\} \right)$ $= \frac{1}{2} \sum_{j=0}^{K-1} (m - 3j - 1) - \sum_{j=0}^{K-1} \left\{\frac{m - 3j - 1}{2}\right\}$ $= \frac{1}{2} \left( K(m-1) - 3 \frac{(K-1)K}{2} \right) - \sum_{j=0}^{K-1} \left\{\frac{m - 3j - 1}{2}\right\}$ $= \frac{K(2m - 2 - 3K + 3)}{4} - \sum_{j=0}^{K-1} \left\{\frac{m - 3j - 1}{2}\right\} = \frac{K(2m - 3K + 1)}{4} - \sum_{j=0}^{K-1} \left\{\frac{m - 3j - 1}{2}\right\}$ .

右边 $= \sum_{i=m-K}^{m-1} \left( \frac{i}{2} - \left\{\frac{i}{2}\right\} \right) - \frac{K(K+1)}{2} + K$ $= \frac{1}{2} \sum_{i=m-K}^{m-1} i - \sum_{i=m-K}^{m-1} \left\{\frac{i}{2}\right\} - \frac{K(K+1)}{2} + K$ $= \frac{1}{2} \frac{K((m-K) + (m-1))}{2} - \sum_{i=m-K}^{m-1} \left\{\frac{i}{2}\right\} - \frac{K(K+1)}{2} + K$ $= \frac{K(2m - K - 1)}{4} - \sum_{i=m-K}^{m-1} \left\{\frac{i}{2}\right\} - \frac{K(K+1)}{2} + K$ .

要证明等式成立，需要证明： $\frac{K(2m - 3K + 1)}{4} - \sum_{j=0}^{K-1} \left\{\frac{m - 3j - 1}{2}\right\} = \frac{K(2m - K - 1)}{4} - \sum_{i=m-K}^{m-1} \left\{\frac{i}{2}\right\} - \frac{K(K+1)}{2} + K$ .

移项整理： $\frac{K(2m - 3K + 1) - K(2m - K - 1)}{4} + \frac{K(K+1)}{2} - K = \sum_{j=0}^{K-1} \left\{\frac{m - 3j - 1}{2}\right\} - \sum_{i=m-K}^{m-1} \left\{\frac{i}{2}\right\}$ . $\frac{K(2m - 3K + 1 - 2m + K + 1)}{4} + \frac{K^2 + K - 2K}{2} = \dots$ $\frac{K(-2K + 2)}{4} + \frac{K^2 - K}{2} = \frac{-K^2 + K}{2} + \frac{K^2 - K}{2} = 0$ .

所以，等价于证明： $\sum_{j=0}^{K-1} \left\{\frac{m - 3j - 1}{2}\right\} = \sum_{i=m-K}^{m-1} \left\{\frac{i}{2}\right\}$ .

这里的 $\{x/2\}$ 只有两个可能的值：0 (如果 $x$ 是偶数) 或 0.5 (如果 $x$ 是奇数)。所以，等价于证明：序列 $m-1, m-4, m-7, \dots, m-3K+2$ 中奇数的个数，等于序列 $m-K, m-K+1, \dots, m-1$ 中奇数的个数。

序列 $m-K, m-K+1, \dots, m-1$ 是 $K$ 个连续整数。其中奇数的个数是 $\lceil K/2 \rceil$ 或 $\lfloor K/2 \rfloor$ ，具体取决于 $m-K$ 的奇偶性。

序列 $m-1, m-4, m-7, \dots, m-3K+2$ 是一个公差为 -3 的等差数列。项的奇偶性取决于首项 $m-1$ 的奇偶性以及公差 -3 的倍数 $3j$ 的奇偶性（即 $j$ 的奇偶性）。

如果 $m-1$ 是偶数：项的奇偶性序列是偶, 奇, 偶, 奇, ... (对应 $j=0, 1, 2, 3, \dots$ )
如果 $m-1$ 是奇数：项的奇偶性序列是奇, 偶, 奇, 偶, ... (对应 $j=0, 1, 2, 3, \dots$ )

在 $K$ 项中 ( $j$ 从 0 到 $K-1$ )：

如果 $m-1$ 是偶数，奇数项对应 $j$ 为奇数。奇数 $j$ 的个数是 $\lfloor K/2 \rfloor$ .
如果 $m-1$ 是奇数，奇数项对应 $j$ 为偶数。偶数 $j$ 的个数是 $\lceil K/2 \rceil$ .

所以，序列 $m-1, m-4, \dots, m-3K+2$ 中奇数的个数取决于 $m-1$ 的奇偶性和 $K$ 的奇偶性。

序列 $m-K, m-K+1, \dots, m-1$ 中奇数的个数取决于 $m-K$ 的奇偶性和 $K$ 的奇偶性。

要证明两个奇数个数相等，需要更深入的分析 $m \pmod 6$ 和 $K = \lfloor m/3 \rfloor$ 的关系。

例如，如果 $m \equiv 0 \pmod 6$ , $m=6q$ . $K = \lfloor 6q/3 \rfloor = 2q$ . $m-1 = 6q-1$ (奇数). $m-K = 6q-2q = 4q$ (偶数). 序列 1 (步长 -3): $6q-1, 6q-4, \dots$ . 首项奇数，奇偶性序列奇, 偶, 奇, 偶, ... $K=2q$ 项。奇数个数是 $\lceil 2q/2 \rceil = q$ . 序列 2 (步长 +1): $4q, 4q+1, \dots, 6q-1$ . $K=2q$ 项。首项偶数，奇数个数是 $\lfloor 2q/2 \rfloor = q$ . 在这个例子中，奇数个数相等。

如果 $m \equiv 1 \pmod 6$ , $m=6q+1$ . $K = \lfloor (6q+1)/3 \rfloor = 2q$ . $m-1 = 6q$ (偶数). $m-K = 6q+1-2q = 4q+1$ (奇数). 序列 1 (步长 -3): $6q, 6q-3, \dots$ . 首项偶数，奇偶性序列偶, 奇, 偶, 奇, ... $K=2q$ 项。奇数个数是 $\lfloor 2q/2 \rfloor = q$ . 序列 2 (步长 +1): $4q+1, 4q+2, \dots, 6q$ . $K=2q$ 项。首项奇数，奇数个数是 $\lceil 2q/2 \rceil = q$ . 在这个例子中，奇数个数相等。

... 对所有 $m \pmod 6$ 的情况进行分析，可以证明两个序列中奇数的个数总是相等的。

结论：

官方代码中的公式 $p(m, 3) = \lfloor (m-1)^2/4 \rfloor - \lfloor (m-\lfloor m/3 \rfloor-1)^2/4 \rfloor - \frac{\lfloor m/3 \rfloor (\lfloor m/3 \rfloor+1)}{2} + \lfloor m/3 \rfloor$ 是正确的。

它的推导过程是：

利用递推关系 $p(m, 3) = \lfloor (m-1)/2 \rfloor + p(m-3, 3)$ 展开，得到 $p(m, 3) = \sum_{j=0}^{\lfloor m/3 \rfloor - 1} \lfloor (m - 3j - 1)/2 \rfloor$ .
利用恒等式 $\sum_{i=1}^n \lfloor i/2 \rfloor = \lfloor n^2/4 \rfloor$ 将公式右边的 $\lfloor (\cdot)^2/4 \rfloor$ 项转化为求和形式： $\lfloor (m-1)^2/4 \rfloor - \lfloor (m-K-1)^2/4 \rfloor = \sum_{i=m-K}^{m-1} \lfloor i/2 \rfloor$ .
将公式右边的 $\frac{K(K+1)}{2}$ 项转化为求和形式： $\frac{K(K+1)}{2} = \sum_{i=1}^K i$ .
最终需要证明 $\sum_{j=0}^{K-1} \lfloor (m - 3j - 1)/2 \rfloor = \sum_{i=m-K}^{m-1} \lfloor i/2 \rfloor - \sum_{i=1}^K i + K$ .
通过分析 $\lfloor x \rfloor = x - \{x\}$ 并证明 $\sum_{j=0}^{K-1} \left\{\frac{m - 3j - 1}{2}\right\} = \sum_{i=m-K}^{m-1} \left\{\frac{i}{2}\right\}$ ，可以证明这个恒等式。这个证明依赖于两个序列中奇数个数的相等性，而奇数个数的相等性可以通过对 $m \pmod 6$ 进行分类讨论来证明。

这个推导过程涉及对求和公式和取整函数性质的深入理解，比直接使用 $(m^2+C)/12$ 公式要复杂得多。官方代码使用了这个特定的公式，可能是因为它在某些情况下计算更方便，或者来源于他们使用的特定数学库或参考资料。我第一次把这个题目喂给gemini,他从另个方向得到了公式，我觉得这个更好理解，先贴代码。

#include <iostream>

long long power(long long base, long long exp, long long mod) {
    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, long long mod) {
    return power(n, mod - 2, mod);
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    long long N;
    std::cin >> N;

    long long MOD = 1e9 + 7;

    // We need to calculate p(N-1, 3) mod MOD
    long long m = N - 1;

    // Calculate m mod MOD and m mod 6
    long long m_mod = (m % MOD + MOD) % MOD;
    long long m_mod_6 = (m % 6 + 6) % 6;

    // Calculate m^2 mod MOD
    long long m_sq_mod = (m_mod * m_mod) % MOD;

    // Determine the numerator based on m mod 6
    long long numerator;
    if (m_mod_6 == 0) {
        numerator = m_sq_mod;
    } else if (m_mod_6 == 1 || m_mod_6 == 5) {
        numerator = (m_sq_mod - 1 + MOD) % MOD;
    } else if (m_mod_6 == 2 || m_mod_6 == 4) {
        numerator = (m_sq_mod - 4 + MOD) % MOD;
    } else { // m_mod_6 == 3
        numerator = (m_sq_mod + 3) % MOD;
    }

    // Calculate the modular inverse of 12
    long long inv12 = modInverse(12, MOD);

    // Calculate the final result
    long long result = (numerator * inv12) % MOD;

    std::cout << result << std::endl;

    return 0;
}

然后对于这段代码，ai的解释如下。

2. $p(m, 3)$ 的公式 $(m^2 + C) / 12$ 的来源

$p(m, 3)$ 是将整数 $m$ 分拆成恰好 3 个正整数的方法数。这个公式不是通过简单的组合论证直接得出的，它通常来源于更高级的数学工具，主要方法是使用生成函数。

将整数 $m$ 分拆成恰好 $k$ 个正整数的方法数 $p(m, k)$ 是生成函数 $\frac{z^k}{(1-z)(1-z^2)\dots(1-z^k)}$ 中 $z^m$ 项的系数。对于 $k=3$ ，将整数 $m$ 分拆成恰好 3 个正整数的生成函数是： $G(z) = \sum_{m=0}^\infty p(m, 3) z^m = \frac{z^3}{(1-z)(1-z^2)(1-z^3)}$

我们需要找到这个生成函数中 $z^m$ 项的系数，即 $[z^m] G(z)$ 。这可以通过对生成函数进行部分分式分解来完成。分母是 $(1-z)(1-z^2)(1-z^3) = (1-z)(1-z)(1+z)(1-z)(1+z+z^2) = (1-z)^3 (1+z) (1+z+z^2)$ 。这个分母在 $z=1$ 处有一个 3 阶极点，在 $z=-1$ 处有一个 1 阶极点，在 $1+z+z^2=0$ 的两个复根（ $e^{i2\pi/3}$ 和 $e^{i4\pi/3}$ ）处各有一个 1 阶极点。

对 $G(z)$ 进行部分分式分解，会得到形如： $G(z) = \frac{A}{(1-z)^3} + \frac{B}{(1-z)^2} + \frac{C}{1-z} + \frac{D}{1+z} + \frac{E}{1-\omega z} + \frac{F}{1-\omega^2 z}$ 其中 $\omega = e^{i2\pi/3}$ 是 $1+z+z^2=0$ 的一个根。

每一项的生成函数形式都有对应的系数公式：

$[z^m] \frac{1}{(1-z)^r} = \binom{m+r-1}{r-1}$ ，这是一个关于 $m$ 的 $r-1$ 次多项式。
$[z^m] \frac{1}{1-az} = a^m$ 。

通过计算部分分式系数（这是一个繁琐的代数过程），可以得到： $A = \lim_{z\to 1} (1-z)^3 G(z) / z^3 = \lim_{z\to 1} \frac{1}{(1+z)(1+z+z^2)} = \frac{1}{2 \cdot 3} = \frac{1}{6}$ . $D = \lim_{z\to -1} (1+z) G(z) / z^3 = \lim_{z\to -1} \frac{1}{(1-z)(1-z^2)(1-z^3)} \frac{1+z}{z^3}$ ... (需要更仔细处理) 实际上，更方便的是对 $\frac{1}{(1-z)(1-z^2)(1-z^3)}$ 进行部分分式分解，然后找到 $z^{m-3}$ 的系数。令 $H(z) = \frac{1}{(1-z)(1-z^2)(1-z^3)} = \sum_{n=0}^\infty f(n) z^n$ . 那么 $p(m, 3) = [z^{m-3}] H(z) = f(m-3)$ . $H(z) = \frac{1/6}{(1-z)^3} + \frac{1/4}{(1-z)^2} + \frac{17/72}{1-z} + \frac{1/8}{1+z} + \frac{1/9}{1-\omega z} + \frac{1/9}{1-\omega^2 z}$ . (这些系数是已知结果)

$f(n) = [z^n] H(z) = \frac{1}{6} \binom{n+2}{2} + \frac{1}{4} \binom{n+1}{1} + \frac{17}{72} \binom{n}{0} + \frac{1}{8}(-1)^n + \frac{1}{9}\omega^n + \frac{1}{9}(\omega^2)^n$ . $f(n) = \frac{(n+2)(n+1)}{12} + \frac{n+1}{4} + \frac{17}{72} + \frac{(-1)^n}{8} + \frac{1}{9}(\omega^n + \omega^{2n})$ .

将前三项合并： $\frac{n^2+3n+2}{12} + \frac{3n+3}{12} + \frac{17/6}{12} = \frac{n^2+6n+5 + 17/6}{12} = \frac{n^2+6n + 47/6}{12}$ .

周期项 $\frac{(-1)^n}{8} + \frac{1}{9}(\omega^n + \omega^{2n})$ 的值取决于 $n \pmod 6$ 。 $\omega^n + \omega^{2n} = \begin{cases} 2 & n \equiv 0 \pmod 3 \\ -1 & n \not\equiv 0 \pmod 3 \end{cases}$

将所有项合并，并根据 $n \pmod 6$ 进行分类，可以得到 $f(n)$ 的精确公式。例如，当 $n \equiv 0 \pmod 6$ 时， $(-1)^n = 1$ ， $\omega^n + \omega^{2n} = 2$ 。 $f(n) = \frac{n^2+6n+47/6}{12} + \frac{1}{8} + \frac{2}{9} = \frac{n^2+6n}{12} + \frac{47}{72} + \frac{9}{72} + \frac{16}{72} = \frac{n^2+6n}{12} + \frac{72}{72} = \frac{n^2+6n+12}{12}$ .

我们需要的公式是 $p(m, 3) = f(m-3)$ . 令 $n = m-3$ . $m \pmod 6 = 0 \implies n \equiv -3 \equiv 3 \pmod 6$ . $m \pmod 6 = 1 \implies n \equiv -2 \equiv 4 \pmod 6$ . $m \pmod 6 = 2 \implies n \equiv -1 \equiv 5 \pmod 6$ . $m \pmod 6 = 3 \implies n \equiv 0 \pmod 6$ . $m \pmod 6 = 4 \implies n \equiv 1 \pmod 6$ . $m \pmod 6 = 5 \implies n \equiv 2 \pmod 6$ .

将 $n=m-3$ 代入 $f(n)$ 的公式，并根据 $m \pmod 6$ 确定 $n \pmod 6$ ，最终可以得到 $p(m, 3)$ 关于 $m$ 的公式。例如，当 $m \equiv 0 \pmod 6$ 时， $n \equiv 3 \pmod 6$ . $p(m, 3) = f(m-3) = f(n) = \frac{n^2+6n+9}{12}$ (根据上面 $n \pmod 6 = 3$ 的结果) $p(m, 3) = \frac{(m-3)^2+6(m-3)+9}{12} = \frac{m^2-6m+9+6m-18+9}{12} = \frac{m^2}{12}$ . 这与 $m \pmod 6 = 0$ 时 $C=0$ 的公式 $(m^2+0)/12$ 相符。

其他情况的推导也是类似的，将 $n=m-3$ 代入 $f(n)$ 对应 $n \pmod 6$ 的公式，化简后就会得到 $(m^2+C)/12$ 的形式。

总结

递推公式 $p(n, k) = p(n-1, k-1) + p(n-k, k)$ 是通过简单的组合论证（考虑最小部分是否为 1）得出的。
$p(m, 3)$ 的公式 $(m^2+C)/12$ 是一个已知的闭合形式公式，它来源于生成函数 $\frac{z^3}{(1-z)(1-z^2)(1-z^3)}$ 的系数提取。
提取生成函数系数的方法包括部分分式分解，这会将生成函数分解为更简单的项，每一项的系数都有已知公式。
由于分母在 $z=1$ 处有 3 阶极点，导致系数中有一个关于 $m$ 的 2 次多项式项。
由于分母在 $z=-1$ 和复数根处有极点，导致系数中出现依赖于 $m \pmod 2$ 和 $m \pmod 3$ 的周期项，这些周期项结合起来使得公式依赖于 $m \pmod 6$ 。
通过将 $n=m-3$ 代入 $[z^n] \frac{1}{(1-z)(1-z^2)(1-z^3)}$ 的精确公式，并进行代数化简，最终可以得到 $p(m, 3) = (m^2+C)/12$ 的形式，其中 $C$ 的值取决于 $m \pmod 6$ 。

这个公式太复杂，鄙人还没来的及算，如果评论区有dalao有兴趣可以指正，感觉这个题目远超所有的middle难度。