P6189【题解】 [NOI Online 入门组] 跑步

皎月半洒花

2020-03-07 22:49:32

Solution

其实就是分拆数问题。分拆数问题本质上是 $n$ 也无标号的第二类斯特林数问题(第二类斯特林数是 $n$ 有标号但是 $k$ 无标号)。 那么对于这个问题,考虑两种 $dp$. * 1、令 $f_{i,j}$ 表示对于 $i$ 拆分成若干个不大于 $j$ 的数的方案数。则有转移: $$f_{i,j}=f_{i,j-1}+f_{i-j,j}$$ 后面一项 $f_{i-j,j}$ 可以看成一个背包一样,后面的状态对前面的状态有天然的累加效应,所以只需要考虑丢掉一个 $j$ 的情况;而前面一项则把我们转移从后一项的**等于** $j$ 升级成为**不大于** $j$ 。 * 2、令 $g_{i,j}$ 表示对于 $i$ 拆分成 $j$ 个数的方案数。则有转移: $$g_{i,j}=g_{i-1,j-1}+g_{i-j,j}$$ 前面一项表示新拆出一个 $1$ 来,还是背包的那种“累加”思想,所以只需要考虑拆出一个 $1$ 的情况;后面一项则表示不拆,而是把拆出的数全体都 $+1$,即本来的 $5=3+1+1$ 转移到 $8=4+2+2$ 。注意此处不会存在“部分拆出来的数加了但是剩下的没加”或者“加的不一样”,因为这两个状态都是可以归约到 $i$ 较小的 $g$ 上去所以不需要额外转移。 ps:似乎某硬币xx的容斥题就用到了这个思想来着。。。实际上就是个背包吧qaq 但是上述做法是 $n^2$ 的。总结两个 $dp$ 的优劣,发现如果采用根号分治的策略,对于 $f$ 只转移 $< \sqrt n$ 的,对于 $g$ 只转移 $\geq \sqrt n$ 的,那么两者均只需要 $n\sqrt n$ 的时空代价(因为大于 $\sqrt n$ 的数不会用超过 $\sqrt n$ 个)。 具体的,考虑对先用 $f$ 求出来 $j< \sqrt n$ 的方案数,再魔改一下 $g$,让 $g$ 只转移那些 $\geq \sqrt n$ 的数字:就是第一维把 $\sqrt n$ 当作步长转移即可。 之后考虑如何合并答案。发现 $f,g$ 对于同一个 $n$,计数的部分互斥且互补,那么就可以直接乘法原理解决。合并是个卷积状物,但由于本题只需要求第 $n$ 项,所以直接算即可。 ```cpp const int B = 403 ; const int N = 200010 ; int S ; int ans ; int n, p ; int f[N][B] ; int g[N][B] ; int X[N], Y[N] ; int main(){ cin >> n >> p ; S = n / B + 1 ; X[0] = 1 ; for (int i = 0 ; i < B ; ++ i) f[0][i] = 1 ; for (int j = 1 ; j < B ; ++ j) for (int i = 1 ; i <= n ; ++ i){ if (i < j) f[i][j] = f[i][j - 1] ; f[i][j] = (f[i - j][j] + f[i][j - 1]) % p ; X[i] = f[i][j] ; //cout << i << " " << X[i] << endl ; } g[B][1] = 1 ; Y[0] = 1 ; for (int i = 0 ; i <= n ; ++ i) for (int j = 1 ; j <= S && j <= i ; ++ j){ if (i >= B) (g[i][j] += g[i - B][j - 1]) %= p ; if (i >= j) (g[i][j] += g[i - j][j]) %= p ; } for (int i = 0 ; i <= n ; ++ i) for (int j = 1 ; j <= S ; ++ j) (Y[i] += g[i][j]) %= p ; for (int i = 0 ; i <= n ; ++ i) (ans += 1ll * X[i] * Y[n - i] % p) %= p ; cout << ans << endl ; return 0 ; } ```