【日常小测】Hope

题目大意

给定排列的长度$n(n\le10^5)$和常数$k(k\le10^5)$
对于单个排列$A$中的每$i$位:我们连一条从$i$出发,到其右边第一个比它大的位,如果没有就不连
定义$A$的花费为 $\sum$其中每一个连通块的大小$^k$
询问所有长度为$n$的排列的花费和$(\bmod 998244353)$

解题报告

设$f_i$为排列长度为$i$的答案,假设我们已经求出了$f_{i-1}$
我们考虑枚举$i$放在哪里,那么$i$之前的数全部连向$i$,之后的数是递归一个子问题
于是我们可以写出暴力的$DP$:${f_i} = \sum\limits_{j = 1}^i {{j^k}(j – 1)!C_{i – 1}^{j – 1}{f_{i – j}}} $
我们化一化式子可以得到$\frac{f_i}{(i-1)!}=\sum\limits_{j=1}^{i}{j^k \cdot \frac{f_{i-j}}{(i-j)!}}$
这显然是一个卷积的形式,于是可以用$NTT$优化

另外,对于$f_i$来讲,$f_{1 \sim i-1}$都会对它有贡献
那么这有是一个典型的$CDQ$分治的模型,于是我们还需要套上一个$CDQ$分治

在另外的话,我们回顾一下推出暴力$DP$的过程
不难发现我们是以最大值的插入作为突破口
那么这种题目与最大值相关的问题,这应该算是套路之一吧!
例如:HDU 5575

—————————— UPD 2017.3.17 ——————————
Claris说这题在OEIS上能找到$O(n)$的递推式 QwQ
Claris太强啦! _(:з」∠)_

2 thoughts to “【日常小测】Hope”

  1. I’ve been exploring for a bit for any high quality articles or blog posts on this kind of area . Exploring in Yahoo I at last stumbled upon this web site. Reading this info So i’m happy to convey that I have a very good uncanny feeling I discovered exactly what I needed. I most certainly will make sure to do not forget this site and give it a glance regularly.

发表评论

电子邮件地址不会被公开。 必填项已用*标注