123
M
先考虑把 \(n\) 分为偶数段的情况。大于小于不能同时做，考虑容斥，计算 \(a_1<a_2?a_3<a_4?\dots?a_{2k-1}<a_{2k}\) 的个数，其中 \(?\) 要么是 \(\leq\)，要么是没有限制。设 \(a(n)\) 表示把 \(n\) 分为偶数段似严格递增形如 \(a_1<a_2\leq a_3<a_4\leq\dots\leq a_{2k-1}<a_{2k}\) 的所有方案的权值和，一个方案的权值为 \(-1^{\leq 的个数}\)。那么由容斥原理，记 \(c(n)\) 表示把 \(n\) 划分为偶数段的方案数，有
\[ c(n)=\sum_{k=0}^{\infty}\sum_{\substack{n_i\geq 0\land 2|n_i \\ n_1+\dots+n_k=n}}a(n_1)a(n_2)\dots a(n_k) \]
这个式子可以用生成函数表示，令 \(A(x)=\sum_{n\geq 0}a(n) x^n\)，\(C(x)=\sum_{n\geq 0}c(n)x^n\)，有
\[ C(X)=\sum_{k\geq 0}^{\infty}A(x)^k=\frac{1}{1-A(x)} \]
那么如果能求出 \(A(x)\)，就能通过多项式求逆求出 \(C(x)\)，考虑如何求 \(a(n)\)，注意到对于一个似严格递增序列，有 \(a_i\geq i/2\)，那么这个序列的长度是 \(O(\sqrt n)\)量级的，就可以通过 dp 求出。记 \(a(n,l)\) 表示长度为 \(l\) 的形如 \(\dots\leq a_{l-1}<a_l\) 序列的权值和为 \(n\) 的方案数，考虑增长长度时往前加，有转移
\[ \begin{aligned} a(n,l)\to a(n+l,l)\quad & \\ a(n,l)\to a(n+l+1,l+1)\quad & if\ l\ odd \\ a(n,l)\to a(n+1,l+1)\quad & if\ l\ even \end{aligned} \]
注意在求 \(A(x)\) 的时候需要根据长度确定 \(-1\) 的次幂。
考虑把 \(n\) 划分为奇数段的情况，有两种情况，用类似手段处理
- \(a_1<a_2>a_3<a_4>a_5\to a_1<a_2?a_3<a_4?a_5\)
- \(a_1>a_2<a_3>a_4<a_5\to a_1?a_2<a_3?a_4<a_5\)
观察容斥的形状，可以发现由一段长度奇数加上若干段长度偶数的段组成，偶数的段可以复用上面的结果。考虑奇数段，两种情况的奇数段形状为 \(\dots a_{l-2}<a_{l-1}\leq a_l\) 与 \(\dots a_{l-2}\leq a_{l-1}<a_l\)，第二种情况可以直接由 \(a(n,l)\) 求出，第一种情况考虑类似dp，令 \(b(n,l)\) 表示长度为 \(l\) 的形如 \(\dots<a_{l-1}\leq a_l\) 序列的权值和为 \(n\) 的方案数，其转移类似于 \(a(n,l)\)，可以求出。那么记 \(c_1(n)\) 为情况1的方案数，记 \(b_1(n)\) 为把 \(n\) 分为第一种段的方案数，有
\[ c_1(n)=\sum_{2\nmid t}b_1(t)c(n-t) \]
简单多项式乘法即可求得，第二种情况同理。
总时间复杂度 \(O(n\sqrt n)\)，具体实现时可以对dp的第二维滚动节省空间。
I
哎这个几何题
假设我们知道对称中心是 \(X\)，那么令\(Q_i=2X-P_i\)，则\(P_i,Q_i\)共\(2n\)个点都在凸包上。求这\(2n\)个点的凸包，如果这\(2n\)个点都在凸包上，不难说明这个凸包一定中心对称，并且如果确定\(X\)的话这个凸包就是最小面积的、所有点都在凸包上的、凸包中心对称的答案。
题解的做法很简单。给定的 \(P_{1,...,n}\) 是凸包，那么考虑 \(n^2\) 条直线 \(\frac{P_i+P_j}{2}\frac{P_i+P_{j\ mod\ n+1}}{2}\)，把这\(n^2\)条直线生成的\(n^4\)个交点都作为\(X\) checkmin一遍答案就行了。
为什么正确呢？题解给了具体证明。简单的说，\(n^2\)条直线生成了\(n^4\)个区域。如果把相同区域内的点作为\(X\)的取值，可以证明\(P_i,Q_i\)共\(2n\)个点中，每一个点相对于每个一点的极角顺序都不变。也就是，\(X\)在当前区域内乱动，生成的凸包包含哪些点、凸包上点的顺序都是不会改变的。如果区域内某个\(X\)的取值合法，这个区域的\(X\)都合法。然后，不难猜想，这个区域内\(X\)的取值都合法，那么\(X\)生成的凸包的最大值应该在边界处取到。他应该是一个多个一次斜面累加得到的一个东西，应该还是一个一次的、单方向的斜面，最大值应该在这个区域的某个顶点处取到。因此，枚举这些直线的交点就行了。
要敢于猜啊，这个结论不好想的，虽然如果感觉来了可以yy出来，但是很难的吧。