数学
[NOI2018] 冒泡排序
问题转化，反证法可以得到，合法排列的充要条件是不存在编号递增的三个数，满足 (a>b>c) 。
对于合法排列，从左往右讨论每个位置，如果大于前缀 (max) ，就放到 (A) 序列，否则放到 (B) ，则 (A,B) 都是上升序列。
(f(i,j)) 表示前 (i) 个位置放完，最大的数是 (p) ，没有放的数中 (<p) 的有 (j) 个的方案数。
(i+1) 位置放没有放的最小的数， (f(i,j) ightarrow f(i+1,j-1)) 。
(i+1) 位置放没有放的，比 (p) 大的数中，第 (k) 小的数， (f(i,j) ightarrow f(i+1,j+k-1)) 。
有一些限制，比如 (i+j le n) 。
如果没有字典序限制，考虑从 ((0,0)) 到 ((n,0)) ，每次 (x+1) ， (y+k,kge -1) ，方案数就是 (f(n,0)) 。
用括号序列一一对应这个过程， (f(n,0)=(^{2n}_{n})-(^{2n}_{n+1})) 。
考虑字典序的限制，类似数位 DP ，讨论前 (i-1) 位放和题目给出的排列相同的数，第 (i) 位比其大 (1) ，之后随意填数的方案数，加起来就是答案。
这时候其实是从 ((x,y)) 到 ((n,0)) ，在括号序列上的意义就是，已经有 (t) 个左括号在左边固定了，还有 (m) 个右括号以及 (m-t) 个左括号要填。
方案数 ((^{2m-t}_{m})-(^{2m-t}_{m+1})) 。推导方式类似上面 (f(n,0)) 那个式子。
(f(n,0)) 就是 Catalan 数，表示成两个组合数的差，考虑随意填，再减去非法方案数。
非法方案的理解方式我知道的有两种。
一种是把起点从 ((0,0)) 改为 ((0,-2)) ，再把一部分路径沿 (y=-1) 对称。
还有一种是在第一次出现非法，即 ([]] cdots) 的情况时，交换左右括号，得到 (][[ cdots) ，这样 ([) 的数量 (+1) 。
题外话，如果把 DP 状态改为 (>p) 的数，会得到一个可以用后缀和优化的方程，再搞和式。而如果把第二维 (j) 反过来，就是说变成 (n-i) ，似乎前缀和 (g) 可以推得 (g(0,0)=1,g(i,j)=g(i-1,j)+g(i,j-1)=(^{i+j-1}_{j-1})) （加一减一我可能记错了），然后再怎么怎么搞……
这题网上做法特别多，题解都写得极其抽象，太……妙……了。
[LOJ 6363] 地底蔷薇
首先，吃一发 [BZOJ 3456] 城市规划 ， (n) 个有编号点的无向连通简单图数量。
吃饱了，再见。
苹果树
先求 (n) 个 (ge 0) 的点，点权和 (le lim) 的方案数。
枚举点数 (k) ，再枚举 (k=a+b) ，分成两半，分别暴力统计点数和对应的权值，有 (2^20) 个。
然后用 meet-in-the-middle 线性合并得到 (k) 的方案数。
好点，坏点，有贡献的点，连边，矩阵树定理。
此时有贡献的点并不一定有贡献，需要容斥。
(f(n)) 表示恰好 (n) 个有贡献的点方案数，是要求的。 (g(n)) 是矩阵树定理求出来的 (le n) 个有贡献的方案数。
总结起来，枚举好点数 (k) ，矩阵树定理算 (g) ，计算 (f) ，加到答案里。