[NOI Online #1 入门组] 跑步 题解
一个经典问题：计数将正整数\(n\)拆分为若干个正整数的方案数，这里拆成的正整数是无序的，对\(P\)取模。
容易得到\(O(n^2)\)解法
设\(f_{i,j}\)表示用\(j\)个数得到\(i\)的方案数。转移即考虑增加一个数为\(1\)或全部数加\(1\)。
或者设\(f_{i,j}\)表示用\(\le j\)的数得到\(i\)的方案数。转移即考虑选不选\(j\)。
然而似乎无法继续优化。
下面就是本题的关键了。画出\(\text{Ferrers}\)图，如图
\[\begin{matrix} &\circ &\circ &\circ &\circ &\circ &\circ\\ &\circ &\circ &\circ &\circ\\ &\circ &\circ &\circ\\ &\circ &\circ\\ &\circ &\circ\\ &\circ \end{matrix} \]这里将一行看成一个数。
考虑上面的\(O(n^2)\)做法在\(\text{Ferrers}\)图上的实质。
第一种做法是每次在下方加一个点或在左方加一列。复杂度为\(O(n \times 行数)\)。
第二种做法是每次加一行或者将当前可加行长度加一。复杂度为\(O(n \times 列数)\)。
我们想要将行数和列数同时控制在一个合适的范围内，这样把两个做法拼起来或许就能优化。
于是考虑强制第一种做法中每加一个点就加\(B\)个，第二种做法中至多将当前可加行长度累加至\(B - 1\)
这样第一种做法中行数至多为\(\frac{n}{B}\)复杂度就是\(O(\frac{n^2}{B} + nB)\)
取\(B = \sqrt{n}\)，可得最优复杂度为\(O(n\sqrt{n})\)
点我看代码 |ू･ω･` )
#include <cstdio>
#include <iostream>
#define LL long long
using namespace std;
template <typename T>
inline void read(T &x) {
x = 0; int f = 0; char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
if(f) x = ~x + 1;
}
const int B = 317;
const int N = 1e5 + 10;
int n, P, m, ans;
int f[N][B + 10], g[N][B + 10];
LL sg[N];
inline void update(int &x, int y) {if((x += y) >= P) x -= P;}
int main() {
read(n), read(P);
for(int i = 0; i <= B; ++i) f[0][i] = 1;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j < B; ++j) {
f[i][j] = f[i][j - 1];
if(i >= j) update(f[i][j], f[i - j][j]);
}
}
m = n / B + 1;
sg[0] = g[0][0] = 1;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
if(i >= B) update(g[i][j], g[i - B][j - 1]);
if(i >= j) update(g[i][j], g[i - j][j]);
sg[i] += g[i][j];
}
sg[i] %= P;
}
for(int i = 0; i <= n; ++i)
update(ans, f[i][B - 1] * sg[n - i] % P);
printf("%d\n",ans);
}