比赛链接:https://atcoder.jp/contests/keyence2021
F - Keyence Repetition
设 \(f_i\) 是第 \(i\) 个字符再哪个循环里。显然 \(f_i\le f_{i+1}\),那么我们只需要确定有几个严格 \(<\) 即可,其他都取等。这样方案数就是 \(\binom{n}{m}\),其中 \(m\) 是不同的数的个数。那么这个显然可以 \(dp[l][r][state_l][state_r]\) 代表 \([l,r]\) 这一段,左边在循环中的状态是 state_l,右边是 state_r 的多项式。这样直接分治复杂度 \(O(27nlog^2n)\) 勉强能冲。
然后发现除了 e 的部分都不需要那个 27 的常数,而 e 的部分又可以倍增,于是常数就下来了。然后又发现倍增可以和枚举状态分开了,于是就 \(O(kn+n\log n)\) 了。
code(当然是前者,后者狗都不写)。