0xABC
B
By Nerovix
[galaxy brain meme]题
一个男舞伴要匹配两个女舞伴，那就把男舞伴拆成两个分身
考虑如下建图：对每个男舞伴建点\(u_i,u_i'\)，并连接\(u_i,u_i'\)。然后对每个女舞伴建点\(v_j\)，如果男舞伴\(i\)能和女舞伴\(j\)匹配，连接\(u_i,v_j\)和\(u_i',v_j\)。求这个一般图的最大匹配，减去\(n\)就是答案。
考虑证明。只需证明以上一般图的匹配可以和原二分图的二重匹配互相构造。给定原二分图的一个二重匹配，很容易构造出在一般图上的一个匹配；给出一般图上的一个匹配：若\(u_i,u_i'\)匹配了两个不同的女伴，那么这三人在原二分图上达成匹配，否则\(u_i,u_i'\)中有一个匹配了女伴且另一个无匹配，或者\(u_i\)与\(u_i'\)匹配，这两种情况都对应男舞伴\(i\)在原二分图无匹配。由此两个图上的匹配能够互相构造，因此求一般图上的最大匹配即可。
I
首先有一个观察，只考虑不被覆盖的那些 Interval，那么要么两两不相交，要么只有两个且并为整个排列。
对于两两不相交的那些非法排列，记 \(g_{n,k}\) 为长为 \(n\) 的排列分为 \(k\) 段，每段自由排列的方案，这个可以 \(O(n^3)\) 求得。然后两两不相交的非法排列个数为 \(\sum_{k = 2}^{n - 1}ans_k\cdot g_{n,k}\)，\(ans_k\) 为长为 \(k\) 的 Interval Free 排列数。
对于只有两个的非法排列，若相交，容易化为两不交的，便于讨论不妨记靠前的为 \([1,k]\)，考虑所有两个不交的相邻 Interval，由于此时不保证 Interval 不被覆盖，为避免重复，计算时需要保证前面没有更小的为满足的。记为 \(f_i\)，直接减去不合法的有 \(f_n = n!-\sum f_i(n - i)!\) 。
综上，有答案式子为总共的减去不合法的 \(ans_n = n!-2\sum f_i(n-i)!-\sum ans_k g_{n,k}\)
J
By Margarita
模拟题+编译原理题，直接模拟就好，不过Parse的复杂度要控制在\(O(\text{串长})\)以内，或者外面实现好点，不然总复杂度会爆。