P6189【题解】 [NOI Online 入门组] 跑步
皎月半洒花
2020-03-07 22:49:32
其实就是分拆数问题。分拆数问题本质上是 $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 ;
}
```