老忘后缀数组咋写,写个东西记录下。
算法核心:因为后缀是在同一个串内的,要充分利用其它信息。
提前介绍一下广义的组合数,组合数 \(\tbinom{n}{m}\) 的定义是 \(\frac{n\times (n-1)\times ... \times (n-m+1)}{m!}\),广义下的组合数只需要保证 \(m\) 为非负整数,\(n\) 可以是任意实数。
对于一个多项式 \(\sum_{i=0}^{\infty}a_ix^i\),如果我们只关心它的各项系数 \(\{a_0,a_1...\}\),而并不关心 \(x\) 的值以及其收敛或发散的问题,就可以说其是关于 \(x\) 的形式幂级数。
总结一些有关莫比乌斯函数的应用以及一些数论方面的东西。
一道极 (e) 妙 (xin) 的自动机优化 DP 的题目。
先假设最后得到的字符串为 \(T\),由题意易知 \(T\) 合法当且仅当 \(T\) 是回文串且 \(S\) 是 \(T\) 的一个子序列。
\(T\) 是回文串的这个性质我们可以通过从外向内一个一个填字符来实现,所以我们需要 DP 的是 \(S\) 相对于 \(T\) 而言被匹配了多少个字符。
特别的,因为当 \(T\) 的长度为奇数的时候,最后一次填的字符本质上是一个字符,需要特别处理,所以下面我们先讨论 \(T\) 的长度为偶数的情况。
我们还在这样的世上活着;我也早觉得有写一点东西的必要了。离十一月十六日只不足几天,CSP 的审判快要降临了罢,我正有写一点东西的必要了。(雾