168 CFgym103469J Joke
首先把 \(p\) 变形为恒等排列以方便处理。
可以发现，一个 \(s\) 合法当且仅当连成图后不成环。
由于环一定会跨越两行，而简单环一行内若有 \(>2\) 个数总能变成 \(2\) 个数，因此只需考察大小为 \(4\) 的简单环。
我们按照 \(q\) 的大小，从大到小考虑每个下标 \(i\)。若我们让 \(p\) 向 \(q\) 连边，则一定不会成环；如果我们让 \(q\) 向 \(p\) 连边，那么其右边所有还未连边的数都必须让 \(q\) 向 \(p\) 连边。
也就是说，我们要么删去最大元素，要么删去最大元素与其后面所有元素，求删完的方案数。
容易发现，这个值等于 \(q\) 的上升序列个数。
计数比较简单，直接 dp 前 \(i\) 个数，最后一个是 \(j\)，填了 \(k\) 个通配符，前缀和优化即可 \(O(n^3)\)。
据说这是“偏序集的序理想与反链的双射”，但是我根本不会这玩意！！
169 CFgym103469L Little LCS
谔谔打表题。
对于任意一对相邻字符 \((s_i,s_{i+1}),(t_i,t_{i+1})\)，可以发现 \(s\) 与 \(t\) 有至少 \(1\) 个相同字符，所以 lcs 长度至少为 \(n\)。
结论：合法串形如：
S=ABABABABAT=CACBCACAC类：即第一个串AB交替，第二个奇数位置为C，其余位置AB任意。S=ACACACBCBT=BCBCBCACA类：即两串偶数位置为C，奇数位置 S 为 \(k\) 个A与 \(n-k+1\) 个B，T 为 \(k\) 个B与 \(n-k+1\) 个A。
结论可以打表发现，通过归纳法与细致的分类讨论可以证明，具体就是枚举长度 \(2n-1\) 的前缀属于哪一类，再枚举后面三个字符的形态。
170 Ptz2017 Winter Xiaoxu Guo Contest 5 H Permutation and noitatumreP
标签：妄自菲薄,连边,字符,30,个数,29 From： https://www.cnblogs.com/xiaoziyao/p/17071980.html