比赛地址pushpush双端队列模拟即可。代码11显然有恰好一个数出现了 $2$ 次,设其出现的两个位置为 $l,r(l<r)$。考虑容斥。长度为 $k$ 的子序列数显然为 ${n+1\choose k}$,但其中有重复的。冷静分析一下可以发现,重复的一定是在 $l-1+(n+1-r)$ 个元素中选了 $k-1$ 个,和某个重复的数组成了子序列。所以答案为 ${n+1\choose k...
Luogu分析容易发现一个性质:一个长度为 $n$ 的串的最小 border 的长度一定不超过 $\left\lfloor\frac{n}{2}\right\rfloor$。第一问考虑 DP。设 $dp_i$ 表示长度为 $i$ 的无界单词的个数,转移时容斥并枚举最小 border 的长度,不难得到第二问,考虑依次确定每个字符。每次先将当前字符设为 a 并计算无界单词的个数 $s$,如果 $...
LuoguBZOJ分析考虑一个 naive 的 DP。设 $f_{i,j}$ 表示前 $i$ 位匹配到不吉利数的第 $j$ 位的方案数。设 $g_{i,j}$ 表示在匹配到第 $i$ 位时加一个字符会匹配到第 $j$ 位的方案数,那么考虑如何求出 $g$。枚举每一位以及后面加的字符,然后爆跳 nxt 即可找到加字符后转移到的位置。然后注意到上面的 DP 式像矩阵乘法的形式,直接矩阵快速幂即可...
AtCoderLuogu分析首先你要知道怎么求一个字符串的循环节。事实上跑 KMP ,然后 $len-nxt[len]$ 就是它的循环节长度了。当然你要判一下这个是不是 $len$ 的约数,不是就没有循环节。那么这题就比较简单了。首先 $m$ 显然只有 $3$ 种取值:$1,2,|w|$ 。然后可以发现,当且仅当循环节长度为 $1$ 时 $m$ 取 $|w|$ ,当且仅当不存在循环节时 $m...
UVaLuoguVjudge分析考虑 Polya 定理。容易得到一个置换的循环个数是 $\gcd(k,P)$ 。于是我们只需要找出所有置换即可。可以使用 KMP 。把原数组倍长,然后求差分数组。于是直接拿原差分数组匹配,能够匹配上的位置就对应着一个置换。代码// =================================== // author: M_sea // websi...
Luogu分析听了 laofu 的讲课并看了 ymd 的论文后做了这题。以下统一规定 $n$ 为字符集大小,$m$ 为名字长度。设 $f_i$ 表示长度为 $i$ 时结束的概率,$g_i$ 表示长度为 $i$ 时没有结束的概率。设 $f_i$ 的概率生成函数为 $F(x)$ ,$g_i$ 的概率生成函数为 $G(x)$ 。根据 YMD 的论文可以知道我们要求的就是 $F'(1)$ 。分析一下...
LuoguBZOJ分析$\mathrm{KMP}$+阅读理解首先翻译一下题目:如果存在串 $B$ ( $B$ 可以为空) ,使得 $A=PB$ ,那么称 $P$ 是 $A$ 的前缀。如果 $A\neq P$ 并且 $P$ 是 $A$ 的前缀,那么称 $P$ 是 $A$ 的 $\mathrm{proper}$ 前缀。如果 $Q$ 是 $A$ 的 $\mathrm{proper}$ 前缀,并且...
LuoguBZOJ分析$\mathrm{KMP}$ 。首先求出 $nxt$ ,然后考虑怎么求 $num$ 。发现 $num$ 的不重叠的限制似乎不太好搞,于是考虑先求出一个没有这个限制的数组 $tmp$ 。发现对于一个前缀 $i$ ,满足既是它的前缀又是它的后缀的串是 $nxt[i]$ 、 $nxt[nxt[i]]$ 、...那么在求 $nxt$ 的时候顺便把 $tmp$ 求出来就行了。具体...
Luogu分析$\mathrm{KMP+DP}$ 。先把 $nxt$ 求出来,考虑怎么 $\mathrm{DP}$ 。设 $f[i]$ 表示前缀 $i$ 的答案。显然 $f[i]$ 只能取 $i$ 或 $nxt[i]$ 。进一步发现, $f[i]$ 取 $nxt[i]$ 仅当存在一个 $j$ ,满足 $f[j]=f[nxt[i]]$ 且 $i-nxt[i]\leq j$ 。实际上不用每次循环...