[NOI Online #1 入门组] 跑步题解

突然发现之前打过 NOI Online，啥都不会的情况下这题竟然拿了 70pts。

思路

题意就是统计对于 $n\le 10^5$，把它进行无序正整数划分的方案数。

对于 70pts，我们考虑 DP：$f_{i, j}$ 表示对于 $1\sim i$，选出来的数的和为 $j$ 的方案数，可以看成完全背包，物品是数字，体积是数字大小，不难列出这个转移方程：

\[f_{i, j} = f_{i - 1, j} + f_{i, j - i} \]

注意 $j$ 要从小到大枚举，这是完全背包的经典优化。

但是这个就算滚动数组也显然会超时。

观察发现，对于 $> \sqrt n$ 的数字，我们不会选择超过 $\sqrt n$ 个，不然就超过 $n$ 了。

所以可以考虑根号分治，对于 $\le \lfloor\sqrt n\rfloor$ 的数字选取方式我们直接用上面的背包 DP；对于 $> \lfloor\sqrt n\rfloor$ 的数字，我们定义 $g_{i, j}$ 表示选择了 $i$ 个 $> \lfloor\sqrt n\rfloor$ 的数字，总和为 $j$ 的方案数。

转移方程如下：

\[g_{i, j} = g_{i - 1, j - (\lfloor\sqrt n\rfloor + 1)} + g_{i, j - i} \]

可以这样理解：

考虑构造一个数组，使得最后为一种合法的 $g_{i, j}$ 情况，那么这个构造的过程一定可以看成是两种操作：

加入新的数，初始为 $\lfloor\sqrt n\rfloor + 1$
给所有数组的数字 $ + 1$

不难发现使用上面两种操作一定可以构造出任意一个合法解，这两种操作对应了上式两个转移。

所以最后统计答案的时候可以枚举 $\le \lfloor\sqrt n\rfloor$ 的数有几个，再枚举 $g$ 中使用了多少个数字。

也就是公式：

\[\sum_{i = 0}^n\sum_{j = 0}^{\lfloor\sqrt n\rfloor}f_{\lfloor\sqrt n\rfloor, i}\times g_{j, n - i} \]

码来！

// Problem: P6189 [NOI Online #1 入门组] 跑步
// Author: Moyou
// Copyright (c) 2023 Moyou All rights reserved.
// Date: 2023-12-05 22:09:15

#include <iostream>
#include <cmath>
using namespace std;
const int N = 1e5 + 10, M = 320;

int n, mod;
int f[N], g[M][N];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> mod;
    int m = sqrt(n);
    f[0] = g[0][0] = 1;
    for(int i = 1; i <= m; i ++)
        for(int j = i; j <= n; j ++)
            f[j] = (f[j] + f[j - i]) % mod;
    for(int i = 1; i <= m; i ++)
        for(int j = i; j <= n; j ++) {
            g[i][j] = g[i][j - i];
            if(j >= m + 1) (g[i][j] += g[i - 1][j - m - 1]) %= mod;
        }
    int ans = 0;
    for(int i = 0; i <= n; i ++)
        for(int j = 0; j <= m; j ++)
            ans = (ans + 1ll * f[i] * g[j][n - i] % mod) % mod;
    cout << ans << '\n';

    return 0;
}