user

1
2
3
4
5
6
7
8
9
10
清理（二）
小朋友有一个“数字毛毛虫”玩具，包含有N片拼板，分别标有编号；如果把它们都拼起来，将会组成一条直线，且按照1到N顺序排列。

每天晚上，小朋友的爸爸都要把玩具房里撒了一地的毛毛虫拼板捡起来。他捡的时候是完全随机的，捡起来之后，再按照正确的顺序拼好。
这样一来，毛毛虫拼板将会构成分离的片段，并且不断合并直到组成完整的毛毛虫。

爸爸每将一块拼板拼到正确的位置上，就会形成一个长度为k的片段，相应地他会写下第k个六边形数k(2k-1)。当爸爸完整地拼完毛毛虫后，他会算出写下的所有数的成绩。有趣的是，这一乘积的期望总是整数。例如，若N=4，则期望值为994。

若毛毛虫拼板共有N=100片，求此时乘积的期望，并对987654319取余作为你的答案。
请给我cpp代码实现和你的思路

deepseek

思路：

  1. 问题转化：正向过程是按随机排列顺序将拼板逐个拼接到正确位置，每次拼接后会产生一个新的连续片段长度 (k)，并写下第 (k) 个六边形数 (f(k)=k(2k-1))。逆向来看，这等价于从完整的毛毛虫出发，每次随机拆下一块拼板，拆下前它所在的片段长度同样为 (k)，也写下 (f(k))。两种过程对同一排列产生的写数乘积相同，且排列均匀随机。
  2. 期望的递推：在逆向过程中，对于长度为 (n) 的完整区间，第一步随机选择一块拆下，所在区间长度必为 (n)，贡献因子 (f(n)=n(2n-1))。拆下后区间分裂为左右两个独立子区间（长度分别为 (k-1) 和 (n-k)），后续过程在子区间内独立进行。设 (Cn) 为长度为 (n) 时的期望乘积，则有：
    [
    C_0 = 1,\qquad C_n = \frac{f(n)}{n} \sum    {i=0}^{n-1} Ci C{n-1-i} = (2n-1) \sum{i=0}^{n-1} C_i C{n-1-i}
    ]
    通过小样例检验（如 (N=4) 得到期望 994）递推完全正确。
  3. 计算：利用上述递推式，从小到大计算 (C_n) 直到 (N=100)，过程中对 987654319 取余即可。时间复杂度 (O(N^2))，在 (N=100) 时完全可行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <vector>

using namespace std;

const long long MOD = 987654319;

int main() {
    int N = 100;
    vector<long long> C(N + 1, 0);
    C[0] = 1;

    for (int n = 1; n <= N; ++n) {
        long long sum = 0;
        // 计算卷积 sum_{i=0}^{n-1} C[i] * C[n-1-i]
        for (int i = 0; i < n; ++i) {
            sum = (sum + C[i] * C[n - 1 - i]) % MOD;
        }
        // 乘以 (2n - 1) 并取模
        C[n] = sum * (2LL * n - 1) % MOD;
    }

    cout << C[N] << endl;
    return 0;
}

fun fact

这个题居然是期望dp,而且因为原始拼起来的时候左右的碎片长度未知所以要倒过来dp…
老了,真是不会了…