题解 CF1580F Problems for Codeforces

· · 题解

非常有趣的一道多项式科技题。

官方题解的复杂度为 O(n\log n\log m)，同时 Elegia 给出了 O(n\log n) 做法。两种做法都非常的 Amazing。

这篇题解主要参考了官方题解的评论中 Elegia 的做法 与 mmaxio 的解析，谨此致谢。

一、n 为偶数

转化题意，令 b_i=\begin{cases}a_i,&i\bmod2=1\\m-1-a_i,&i\bmod2=0\end{cases}，只需 b_i\in[0,m) 且 b_1\le b_2\ge b_3\le\cdots\ge b_{n-1}\le b_n\ge b_1。

保留所有的 \le，对 \ge 进行容斥。先不考虑环的情况，即忽略 b_n\ge b_1 这个条件。

设 f(k) 表示钦定 k 个 \ge 不成立（把 k 个 \ge 改为 <，忽略其余的 \ge）的方案数，则答案为 \displaystyle\sum_{k=0}^{\frac n2-1}(-1)^kf(k)。

在 f(k) 的限制下，\{b_i\} 被分成 \frac n2-k 条形如 c_1\le c_2<c_3\le\cdots<c_{2l-1}\le c_{2l} 的链，且不同链的取值相互独立。容易发现，长度为 2l 的链一共有 f_l=\dbinom{m+l}{2l} 种。

记 F(z)=\displaystyle\sum_{i=1}^\infty f_iz^i。如果忽略 b_n\ge b_1，则方案数 f_0(k)=[z^{\frac n2}]F^{\frac n2-k}(z)，于是答案即为

\begin{aligned} \sum_{k=0}^{\frac n2-1}(-1)^kf(k) &=[z^{\frac n2}]\sum_{k=0}^{\frac n2-1}(-1)^kF^{\frac n2-k}(z)\\ &=[z^{\frac n2}]\sum_{k=0}^{\frac n2-1}(-1)^{\frac n2-k-1}F^{k+1}(z)\\ &=(-1)^{\frac n2-1}[z^{\frac n2}]{F(z)\over1+F(z)} \end{aligned}

现在考虑 b_n\ge b_1 的影响，此时 b_1 所在的链不一定从 1 开始。设这条链的长度为 2l，则 b_1 可以是它的第 1,3,5,\cdots,2l-1 个元素，共 l 种可能。此时方案数 f(k)=[z^{\frac n2-1}]F'(z)F^{\frac n2-k-1}(z)，于是答案即为 (-1)^{\frac n2-1}[z^{\frac n2-1}]\dfrac{F'(z)}{1+F(z)}。

实现上，组合数可以预处理 n 以内阶乘的逆元后递推计算，求出 F(z) 后求逆即可。总时间复杂度 O(n\log n)。

二、n 为奇数

记 m_0=\lfloor\frac m2\rfloor,m_1=\lceil\frac m2\rceil。若 a_i<m_1，则称 a_i 是大的，否则称 a_i 是小的。容易发现相邻的 a_i 不能同时为大的。将 \{a_i\} 视为一个环，则它可以被划分为若干段，每段形如「小大小……小大小」，且每段长度均为奇数。

把所有大的元素减去 m_1，于是 0\le a_i\le m_0。如果 a_i=m_0，则 m 为奇数，a_i 原来是小的元素，且 a_i 两侧均不是大的，即 a_i=m_0 只能在长度为 1 的一段取到，特殊处理即可。

设 p_d 表示长度为 2d+1 的段 \{b_i\} 的方案数。可以发现，问题被转化成类似的形式，而且没有了环的限制。仿照之前的做法，将偶数位的 b_i\gets m_0-1-b_i，则只需 b_i\in[0,m_0) 且 b_1\le b_2\ge b_3\le\cdots\ge b_{2d-1}\le b_{2d}\ge b_{2d+1}。

同样地，设 f(k) 表示钦定 k 个 \ge 不成立的方案数，则 p_d=\displaystyle\sum_{k=0}^d(-1)^kf(k)。

在 f(k) 的限制下，\{b_i\} 同样被分成了 d-k+1 条链。与之前不同的是，最后一条链的长度为奇数 2l+1，一共有 g_l=\dbinom{m_0+l}{2l+1} 种。其它链的长度均为偶数，方案数与 n 为偶数且忽略环的情况相同。

记 G(z)=\displaystyle\sum_{i=0}^\infty g_iz^i，则 f(k)=[z^d]F^{d-k}(z)G(z)（这里的 F(z) 即 n 为偶数情况的），所以 p_d=(-1)^d[z^d]\dfrac{G(z)}{1+F(z)}。

记 P(z)=\displaystyle\sum_{i=0}^\infty p_iz^i={G(-z)\over1+F(-z)}。注意当 m 为奇数时，P(z) 还要加上 1z^0，对应单独一段 a_i=m_0 的情况。

同样地，设 b_1 所在的段的长度为 2d+1，则 b_1 可以是它的第 1,2,3,\cdots,2d+1 个元素，共 2d+1 种可能。

记 Q(z)=\displaystyle\sum_{i=0}^\infty(2i+1)p_iz^i，则答案为 \displaystyle[z^{\frac{n-1}2}]Q(z)\sum_{i=0}^\infty z^iP^{2i}(z)=[z^{\frac{n-1}2}]{Q(z)\over1-zP^2(z)}。这里的 zP^2(z) 是因为总段数一定是奇数，除第一段外剩下偶数段，而长为 2a+1,2b+1 的两段总长为 2(a+b+1)，所以还要再乘一个 z。

代码实现同 n 为偶数的情况，但多了一些多项式变换。时间复杂度仍为 O(n\log n)。