Solution Set -「LOCAL」冲刺省选 Round I
\(\mathscr{Summary}\)
??状态还行叭。
??A 题又犯坏习惯，走起来就大力分讨，上了个厕所之后冷静一下开始寻找比较普适性的 DP 状态，然后几乎就切掉了，可惜复杂度写假了没发现（已经预处理过的前缀和一个一个加，笑死）。
??B 题的解法暗示性很强，随便猜一个结点出来套路性 DFS 树就好，比较迅速。
??C 题骗的时候就走得有点偏，问题没有抽象清楚，虽然有暴力分，但和正解毫不相关。这个正解确实太神奇了。
\(\mathscr{Solution}\)
\(\mathscr{A}-\) Sequence
??给定 \(n,k,m,\{a_m\}\)，\(\{a_m\}\) 的值域是 \(U=[1,k]\cap\mathbb N\)。定义值域也是 \(U\) 的序列 \(\{b_n\}\) 是好的，当且仅当它存在一个长度为 \(k\) 的子序列不含重复元素。求在所有的 \(\{b_n\}\) 中，\(\{a_m\}\) 作为连续子序列的出现次数。
??\(m\le n\le2.5\times10^4\)，\(k\le400\)。
??首先，光是 \(\{a_m\}\) 就能让 \(\{b_n\}\) 合法的情况直接判了。
??出现次数，还允许重复，\(n\) 也不大，所以先直接枚举出现位置。设现在 \(\{a_m\}\) 左边还能加 \(l\) 个元素，右边还能加 \(r\) 个元素。注意到若 \(\{a_m\}\) 包含重复元素，左边和右边出现合法段（使 \(\{b_n\}\) 合法的段）的情况是互不影响的，不可能存在跨过 \(\{a_m\}\) 的合法段。稍微抽象一下可以得到这样一个 DP 问题：
??给定一个确定的，长度为 \(j\) 的子序列 \(\{c_j\}\)，在其后面添加 \(i\) 个元素，使得 \(\{c'_{i+j}\}\) 合法，我们记这样的添加方案数为 \(f(i,j)\)，特别地，\(f(i,k)=k^i\)。转移显然有
\[f(i,j)=(k-j)f(i-1,j+1)+\sum_{t=1}^jf(i-1,t). \]可以 \(\mathcal O(nk)\) 得到。两边方案数小小容斥一发就能求到 \(\{a_m\}\) 包含重复元素时的方案。
??不包含重复元素，注意到此时 \(m
注意 \(i-1\) 个不产生重复的元素还会产生 \((k-m)!/(k-m-i+1)!\) 的系数，记得乘上。
??现在算法复杂度是 \(\mathcal O(nk^2)\)，优化很显然：上式对 \(j\) 求和的部分可以滚前缀和。因此最终复杂度为 \(\mathcal O(nk)\)。
\(\mathscr{B}-\) Graph
??给定含有 \(n\) 个结点 \(m\) 条边的强连通有向图，若 \(u\) 到任意结点 \(v\) 都有且仅有一条简单路径，则称 \(u\) 是好的。求出所有好的结点 \(u\)。
??多测，\(\sum n\le10^5\)，\(\sum m\le2\times10^5\)，保证每个图中至少有 \(20\%\) 的好点。
??判 \(u\) 好不好：DFS 一遍，每个访问到的已被遍历过的结点都必须在当前的递归栈内。
??从 \(20\%\) 的条件入手，不要白不要嘛，随便猜几次得到一个好点 \(r\)。这个“好”字对 \(r\) 的限制非常强，分析一下可知：\(r\) 为根的 DFS 树唯一，且仅存在外向树边和返祖边。
??以此为基础，判断其他结点的好不好。对于 \(u\neq r\)，如果 \(u\) 子树内包括两条及以上到 \(u\) 严格祖先的返祖边，显然 \(u\) 不好；否则 \(u\) 子树内必然存在恰好一条到 \(u\) 严格祖先的返祖边（图强连通），如果这个祖先好，\(u\) 就好，否则 \(u\) 就不好。画画图比较明显。
??DFS 一遍求出最浅返祖边和次浅返祖边，再 DFS 一遍判断即可。复杂度 \(\mathcal O(\sum m)\)。
\(\mathscr{C}-\) Shape
??Cov. 「CF 1290F」Making Shapes; .