AGC052 - partly solution
暂时只会了ABC（这就是similar to ABC 吗？）
题目无关的。
本来想写的是『简单题，考场傻逼』了。
但想想，我真的能在不看题解时想到吗？
这真的不好说，在我看题解的那一瞬间，"我能想到"，和"我想不到"两个不确定的状态会瞬间坍塌成"我曾经想不到"这一个状态，时间不会回溯，没看过题解的我也不复存在......
solution
这个题解写的很简单，主要说一下为什么下界是 5。
分成 3 块，\([1,n],[n+1,2n],[2n+1,3n]\)。
ABC每一个数必须在不同的块中取。
和IOI2021 D1T1 的结论类似，只要满足 \(v_A,v_B,v_C=n\) 那么一定有匹配，使得匹配数 \(\leq 5\)。
其次只要每次取，得到的局面一定是更优的，所以一次取最多的一定不劣，正确性显然。
为什么有 \(\leq 5\) 的匹配数？
考虑显然匹配数 \(\leq 6\)，现在考虑取一个 \(ABC\) ，一定是有一块内的 A/B/C 被取光那么对应的轮换肯定取不了所以上界是 5.
waiting
感觉还是挺好玩的。
大概正式AGC时想到了 70% 左右。
我没大看懂Anton的题解,说一下我的心路历程？
solution
首先发现如果当前 LIS 长度是 \(lis\)，那么显然 \(A\) 的值域是 \([lis-1,lis]\)。
当然也可能是单点，这个特殊考虑（只要考虑了就问题不大）。
如果某点 k 在 P 的 LIS 上且是必选的，那么他一定满足 \(A_k=lis-1\) 的，我们叫它 1 类点。
否则有两种情况：这个点在一条我们钦定的 P 的 LIS 上，我们叫他 2 类点；或者他压根不再钦定的 LIS 上，我们叫他 3 类点。这两种情况都是 \(A_k=lis\)。
Q: 感觉似乎就是钦定 1 类点即可？
A :大概是； 我们确实确定出 lis + 0/-1 了，但是不完全，现仍需考虑2类点贡献，他们给 \(lis\) 的值加上了贡献，使 \(lis\) 变长。
考虑 2 类点 k 什么时候能出现，肯定是他前后也有满足 \(\text{pre}_{k}\leq p\leq \text{nxt}_k\)。
前后不好考虑，所以钦定选最靠前的 LIS，那么现在只需要考虑每个 k 到其后继的点中是否有满足 \(\text{pre}_k\leq x\) 的即可。
如果有，k 就是 2 类点，否则就是 1 类点。
也就是说 2 类点 k 后面必然跟着一个点；这个限制其实很松，具体来说我们可以认为在确定出 1 类点后只要 k 和 k 后面第一个一类点间有空位就可以当 2 类点。
写的可能有点杂，梳理一下，我们把问题转化为什么了？
给定空位 n,最长长度 m,你可以把点染成1，2两种颜色，要求2类点必须两个两个在一起，问多少种不同染色方式。
注意 不同 的定义是 1 类点位置不同 或者 2 类点 + 1 类点个数不同。
枚举1，2类点各选几个后，这个 dp 其实比较显然了，但是我通过一些优化只能做到 \(\mathcal{O(n^3)}\) 比较不行。。。
考虑这个 2 类点 “绑定”限制本质是：两个点之间的空位如果是偶数那么没关系，如果是奇数那么就只能 -1（减去1）..
设枚举的是有 \(a\) 个 1 类点，\(b\) 个 2类点。
- 相当于我们有 \(a+1\) 个空位， 我们枚举特殊的奇数个数，然后把他们选出了，他们并不会产生贡献。
- 接下来把 2 类点随意插入，相当于把 \(left\) 拆成 \(a+1\) 个 非负 整数。
- 如此我们顺理成章的确定了 1 类点位置。
答案即为 \(\binom{a+1}{odd}\times\binom{left+a}{a}\)
还是挺有意思的，是吧。
UBUNTU 20.04 输入法是傻逼，一堆错字！！！