Asusetic
0%

2021.11.10模拟赛

发表于 分类于 Valine：
本文字数： 2k 阅读时长 ≈ 2 分钟

To soar above this world

2021.11.10 模拟赛

A. 图

显然 kk 上限是最短路长度，而且只要按最短路跑出来的分层图赋权即可

B. 幂

性价比极高的 80 分做法，枚举括号序列的长度为 kk 答案为 ∑Ck2(nk)(n−k)\sum C_{\frac{k}{2}}\binom{n}{k}(n-k) CiC_i 是卡特兰数

100 分做法需要用生成函数解递推式，性价比不高（但是 T4 又不会做，只能做做 T2 划划水这样子）

试图用生成函数凑出来 80 分式子的人都死了.jpg

考虑拼接括号形成的方案，为了不重复，我们钦定每次拼接都是完整括号或者单独的一个 xx

设方案数数列的生成函数为 F(x)F(x) 则 F(x)=∑(x+x2F(x))i=11−x−x2F(x)F(x)=\sum(x+x^2F(x))^i=\dfrac{1}{1-x-x^2F(x)}

解出来为 F(x)=1−x±1−2x−3x22x2F(x) = \dfrac{1 - x \pm \sqrt{1 - 2x - 3x^2}}{2x^2} 因为 lim⁡x→0F(x)=1\lim\limits_{x \to 0}F(x)=1 所以应该取符号

带权的方案数 G(x)G(x) 类似 这场的道路 的求法，考虑一个序列会被计算多少次，同样是拼接完整括号，即 expr(… )expr(\dots) 中 …\dots 的方案数

这一部分是 x2F(x)G(x)x^2F(x)G(x) 还有拼接一个 xx 的方案数 xF(x)+xG(x)xF(x)+xG(x)

解得 G(x)=(2x)−1((1−x)(1−2x−3x2)−12−1)G(x)=(2x)^{-1}\left((1-x)(1-2x-3x^2)^{-\frac{1}{2}}-1\right)

主要是 (1−2x−3x2)−12(1-2x-3x^2)^{-\frac{1}{2}} 怎么做，考虑解递推式，传统艺能微分表达自身

设 F=G−12F=G^{-\frac{1}{2}} 微分得到 F′=−12G−32G′=−12FGG′F'=-\dfrac{1}{2}G^{-\frac{3}{2}}G'=-\dfrac{1}{2}\dfrac{F}{G}G'

即 F′G=−12FG′F'G=-\dfrac{1}{2}FG' 解出来得到 $(n + 1) f_{n + 1} - 2n f_n - 3(n - 1)f_{n - 1} = f_n + 3f_{n - 1} $

把剩下的 (1−x)(1-x) 对应的差分和 2x2x 对应的除二平移加上就好

C. 异或

考虑一个确定的序列什么时候异或值最小，一定出现在排完序的相邻两项中，证明可以逐位对比得到

所以我们只需要排好序一个一个的做，有 dpi=∑dpj+1(ai⊕aj≥x)dp_i=\sum dp_j+1(a_i \oplus a_j \ge x)

发现这个转移其实是在 Trie 树上求子树和，这样复杂度就是 O(nlog⁡w)O(n\log w) 的

D. 排列

Orz RenaMoe

首先操作 kk 次能得到的排列是含有至少 n−kn-k 的上升子串的排列

容斥，枚举长度至少为 n−kn-k 的上升子串有几个

发现这是错的，因为上升子串重叠应该算作一个

贡献为为 n!∏ai!(−1)x\dfrac{n!}{\prod a_i!}(-1)^{x} xx 和极长上升子串数量，第一部分是个多重集排列

尝试限制上升子串不能重叠发现非常困难，所以考虑合并容斥系数

设 fif_i 表示长度为 ii 的串容斥系数是多少，枚举上一个右端点，强制相交，有 fi=−∑j=1n−kfi−jf_i=-\sum\limits_{j=1}^{n-k}f_{i-j}

于是可以 dpi=∑j=1idpi−jfj1j!dp_i=\sum\limits_{j=1}^{i}dp_{i-j}f_j\dfrac{1}{j!}

再观察下能够发现当 i=(n−k)t+1i=(n-k)t+1 的时候 fi=1f_i=1 当 i=(n−k)ti=(n-k)t 时 fi=−1f_i=-1

所以每次能转移的点只有 n2n−k\dfrac{n^2}{n-k} 个，总体复杂度就是 O(n2log⁡n)O(n^2\log n) 个