文章

容易发现子串有五种形式：$\emptyset,\ s,\ s*,\ *t,\ s*t$，前四种可以建立 suffix automaton 后直接统计，关键在于第五种。 本来想在 $t$ 处统计答案串，但是发现此时找 $s$ 就变成了在 fail 树上找，不太能做。所以不妨考虑 阅读更多…

我水平很菜，你忍一下。 题面 这个题明显的可以定义 $f_i$ 为我打印到 $i$ 点时的最小花费，那么显然我们有 $f_i=\operatorname{min}{f_j+(\sum_{k=j}^i a_k) ^2}, 1\leq j< i$。但是这样做的时间复杂度为 $O 阅读更多…

前言 这篇主要参考了 JOISC 官方题解，算法 2 和 3 两部分可以看作是官方题解的翻译+解释，不过最后的通信量分析和原题解有些出不一样，有兴趣的朋友可以自行翻阅原题解。 这篇文章前前后后咕了 4months，可能中间有一些错误或者不严谨的地方，欢迎批评指正。（应该是全网第一篇？）ps: 算 阅读更多…

该做法不是官方做法。 对于 $n\leq16$ 的部分分可以参考样例解释，直接容斥。 即考虑枚举一定满足的起点集合 $P$。对于某个机器人 $i$，令 $C_{i,j,0/1}$ 表示机器人 $i$，起点为 $p$ 时，如果最开始 $p+j$ 上是 $0/1$，得到的结果是多少。 那么计算此时的方案 阅读更多…

跟着做一遍（挽救一下可怜我的发文量）考虑设 $f_{i,j}$ 表示到第 $i$ 轮，是否有合法方案满足 $a=k_i$ 且 $b=k_j$ 。同样设 $g_{i,j}$ 表示到第 $i$ 轮，是否有合法方案满足 $b=k_i$ 且 $a=k_j$ 。 将转移分成以下几种： $k_i$ 和 $k 阅读更多…

传送门 比赛的时候因为这题罚坐了 80 分钟，已经是废猫了。 题目描述 两个人抽卡，第 $n$张卡的数值为 $a_i$。 刚开始，每人都有一张数值为 0 的卡。 每次两个人必须有一人抽卡，并把自己手上的卡给丢掉。 在第 $i$次抽卡后，两个人的卡面数值需要满足在两个特定的区间内。 问是否有合法的抽卡 阅读更多…

来支持一下 Qiuly /tyt 考虑先进行多点求值，问题转化为对给定的数列 $F_k$ 和 $1 \le m \le n$，计算 $$ \sum\limits_{|\pi|=m} F_{\mathrm{cyc}_{\pi}} $$ 我们自然考察计算 $$ \sum\limits_k F_k \su 阅读更多…

支持一下 Qiuly /tyt 新年的军队题解人话重置版！ 首先作一步相当重要的转化： 对所有满足恰有 $m$ 个位置 $i$ 满足 $\alpha_i > \alpha_{i+1}$ 的实数序列 $\alpha_1,\alpha_2,\dots,\alpha_n$，计算 $\alpha_k$ 的排 阅读更多…

支持一下 Qiuly /tyt 为了膜拜 EI，口胡翻译一下另一个出题人的做法。 上次看的时候没动脑导致完全无法理解，问 EI 他说一年前写的全忘了（看了这个暴力推 GF 做法之后感觉这个双射是从 GF 逆推出来的？ 我们用 $z$ 元计量序列长度，$t$ 元 $t^k$ 的系数表示 $k$ 的出 阅读更多…

支持一下 Qiuly /tyt 令 $k$ 减一。 设 $F_k$ 为 $k+1$ 层树的 EGF。 立刻写出 $$ F_k'(x) = F_{k-1}(x) \left(\frac{ \mathrm e^x+\mathrm e^{-x} }2\right) = F_{k-1}(x) \cosh x 阅读更多…