笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

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

posted on 2020-03-07 22:49:32 | under 题解 |

其实就是分拆数问题。分拆数问题本质上是 $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$ 项,所以直接算即可。

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 ;
}