Skip to content

20261014 计数 笔记 ​

据说是 NFLS 计数专题,高一小灯直呼都是典题,吓哭。

1. CF1874E Jellyfish and Hack ​

首先想一个暴力,利用题目的伪代码逻辑,设 fi,j 表示长度为 i 的序列遍历了 j 次的方案数,先选第 (p+1) 小的出来放到 a1,然后分左右,易得

fi,j←∑p=0i−1(i−1p)∑k=0j−ifp,kfi−p−1,j−i−k

由排序知识可知 j≤i2,因此状态数 O(n3),转移 O(n3),时间复杂度 O(n6)。

发现右边的和式很像多项式卷积的形式,令 Fi(x)=∑j=0+∞fi,jxj,由上文转移方程有(×xi 表示本轮统一加 i 的时间)

Fi(x)=xi∑j=0i−1Fj(x)Fi−j−1(x)

考虑使用拉格朗日插值法,对 Fn(x) 计算出 lim+1 个点值,每个点值需要 n 个多项式进行 n 次计算,因此时间复杂度为 O(n4)。

2. [] ​

最近更新