type = 1
算法 0
爆搜，不过只需要 \(O(2^{2n})\)（钦定绝妙极长连续黑区间段的过程的方案数是平凡的）。
算法 1
考虑一个 DP：设 \(f(i,0/1,j)\) 表示目前考虑到 \(i\)，\(i\) 所在区间是黑色 / 白色，\(i\) 所在区间所在极长连续黑区间段当前长度为 \(j\)（如果存在）的方案数。
转移时枚举 \(i\) 所在区间的开头即可。
首尾不同时取黑色的限制可以暴力加一个状态或是做两次 DP（强制首黑尾白和强制首白尾白）。
时间复杂度 \(O(n^3)\)。
算法 2
考虑优化转移。若枚举的转移点为 \(k\)，则其贡献可以简化为 \(f(k,x,y) \cdot \binom{i-k+1}2\) 或 \(f(k,x,y) \cdot \binom{i-k+1}2 \cdot y\)。
进一步可以简化为 \(f(k,x,y) \cdot k^2,f(k,x,y) \cdot k,f(k,x,y)\) 等，作六个前缀和即可。
时间复杂度 \(O(n^2)\)。
算法 3
在下文提到的正解中忽略 \(w\) 元，使用多项式全家桶计算复合。
时间复杂度 \(O(n \log n)\)。
type = 0
算法 0
直接按照题意爆搜，大概是 \(O(2^{3n})\) 的？
同时可以做到 \(O(2^{2n})\) 但是我太懒了没给这档分。
算法 1, 2
考虑在 type = 1 的 DP 中加入一维记录权值。
时间复杂度 \(O(n^4)\) 或 \(O(n^3)\)。
算法 3
注意到划分区间和选出绝妙子区间的过程和其他部分是独立的，考虑分别计算两个部分。
设 \(f(i,0/1,j,k)\) 表示前 \(i\) 个区间，第 \(i\) 个区间是黑 / 白色，其所在极长连续黑区间段长度为 \(j\)，权值为 \(k\) 的方案数。
容易做到 \(O(n^3)\)。
再另外计算划分区间并选出绝妙子区间的方案数，简单 DP 即可。可以做到 \(O(n^2)\) 或 \(O(n^3)\)。
虽然和算法 2 复杂度一样但是更好写。
算法 4
在下文提到的正解中暴力多项式乘法提取 \(w^s\) 的系数。
时间复杂度 \(O(n^2 \log n)\)。
正解
不难看出一个多项式复合的模型：先计算区间之间的黑白关系，再以每个区间为单位复合。
考虑内层一个区间的 GF： \[ F(x) = \sum\limits_{i\ge 1} \binom{i+1}2 x^i = \frac x{(1-x)^3} \]
对于外层，容易知道所有方案都形如「白黑黑……黑白黑黑……黑白黑黑……黑（白）」（除了首黑尾白，但是根据对称性容易得到这种方案数）。因此可以考虑以形如「白黑黑……黑」的基础单位构造序列来刻画。
令一个极长连续黑区间段的 GF 为（用 \(w\) 元记录权值） \[
G(x) = \sum\limits_{i\ge 1} i x^i w^i (1+w) = \frac{xw(1+w)}{(1-xw)^2}
\]
则答案应当形如 \[ \frac{2+F}{1-F(G \circ F)} \]
由于我们需要求得的仅是 \(x^n\) 项系数，因此可以考虑拉格朗日反演。
注意到 \(F\) 具有简单的封闭形式，从而容易牛顿迭代求出 \(F\) 的复合逆。
然后令 \[
W = \frac{2+x}{1-xG}
\]
则答案为 \[ [x^n]\frac{2+F}{1-FG} = \frac1n [x^{n-1}]W'(x)\left(\frac x{F^{-1}(x)}\right)^n \]
注意 \(-1\) 是函数幂。
然后考虑 \(W'\)： \[ \begin{aligned} W' &= \left(\frac{2+x}{1-\frac{x^2w+x^2w^2}{(1-xw)^2}}\right)' \\ &= \left(\frac{2-4xw+2x^2w^2+x-2x^2w+x^3w^2}{1-2xw-x^2w}\right)' \\ &= \frac{1+4xw^2+x^2w+3x^2w^2-4x^2w^3-4x^3w^3-x^4w^3}{(1-2xw-x^2w)^2} \end{aligned} \]
我们需要提取上式的 \(w^s\) 项系数。
设 \(p(s) = x^s(x+2)^s\)。
则有 \[
\begin{aligned}[]
[w^s]W'
&= [w^s] (1+4xw^2+x^2w+3x^2w^2-4x^2w^3-4x^3w^3-x^4w^3)\sum\limits_{i\ge 0}(i+1)x^i(x+2)^iw^i \\
&= (s+1)p(s)+4(s-1)xp(s-2)+sx^2p(s-1)+3(s-1)x^2p(s-2) \\
&- 4(s-2)x^2p(s-3)-4(s-2)x^3p(s-3)-(s-2)x^4p(s-3)
\end{aligned}
\]
令 \(V = \left(\frac x{F^{-1}}\right)^n\)，则问题变为计算 \(5\) 个 \[ [x^r] \frac{V(x)}{1-tx(x+2)} \]
令 \(P(x)=x(x+2)\)，\(Q(x)=V(P^{-1}(x))\)，\(U(x) = \frac{Q(x)}{1-tx}\)，则根据扩展拉格朗日反演有 \[ [x^r] \frac{V(x)}{1-tx(1+x)} = \frac1r[x^{r-1}]U'(x)\left(\frac x{P^{-1}(x)}\right)^r \]
\(P(x)\) 的复合逆非常好求，就是 \[ \sqrt{1+x}-1 \]
可以随手广义二项式定理展开一下，不嫌麻烦的也可以写个多项式开方。
（但是如果你不会展开的话底下就做不了了）
继续考虑 \[ \begin{aligned} U' &= \left(\frac{Q(x)}{1-tx}\right)' \\ &= \frac{Q'(x)(1-tx)+Q(x)(1-tx)'}{(1-tx)^2} \\ &= \frac{Q'(x)+t(Q(x)-xQ'(x))}{(1-tx)^2} \end{aligned} \]
再令 \(R(x) = \left(\frac x{P^{-1}(x)}\right)^r\)。
则 \[
\begin{aligned}[]
[x^{r-1}t^c]U'(x)R(x)
&= [x^{r-1}t^c]\left(\frac{Q'(x)+t(Q(x)-xQ'(x))}{(1-tx)^2}\right) R(x) \\
&= [x^{r-1}t^c]\left(Q'(x)\sum\limits_{i\ge 0} (i+1)t^ix^i + (Q(x)-xQ'(x))\sum\limits_{i\ge 0}(i+1)t^{i+1}x^i\right) R(x) \\
&= (c+1) [x^{r-c-1}] Q'(x)R(x) + c [x^{r-c}] (Q(x)-xQ'(x))R(x)
\end{aligned}
\]
问题又变为求 \(Q(x)\)。
考虑求 \(V(\sqrt{1+x}-1)\)。
可以首先求 \(V'(x) = V(x-1)\)（记住这个 \('\) 不是求导），然后计算 \(V'(\sqrt{1+x})\)。
这部分可以参考 CF923E。
考虑对系数的奇偶性进行讨论。
对于偶数部分的系数，单独提取出来并复合 \(\sqrt x\)（这个时候就相当于把次数除以二）就变成了复合 \(1+x\)，也比较简单。
对于奇数部分的系数，首先考虑一下 \((1+x)^{i+1/2}\)： \[
\begin{aligned}
(1+x)^{i+1/2}
&= \sum\limits_{j\ge 0} \binom{i+\frac12}j x^j \\
&= \sum\limits_{j\ge 0} x^j \frac{(2i+1)\cdot(2i-1)\cdots(2i-2j+3)}{j!2^j} \\
&= \sum\limits_{j\ge0} x^j \frac{(2i+1)!!}{j! 2^j (2i-2j+1)!!}
\end{aligned}
\]
然后代入系数 \[ \begin{aligned} \sum\limits_{i\ge 0} v'_{2i+1} (1+x)^{i+1/2} &= \sum\limits_{i\ge 0} v'_{2i+1} \sum\limits_{j\ge 0} x^j \frac{(2i+1)!!}{j! 2^j (2i-2j+1)!!} \\ &= \sum\limits_{j\ge 0} \frac{x^j}{j! 2^j} \sum\limits_{i\ge 0} \frac{v'_{2i+1}(2i+1)!!}{(2i-2j+1)!!} \end{aligned} \]
可以卷积解决。
复杂度 \(O(n \log n)\)。
std 最慢点大概是 1.25s。
另外，这份题解是我一段时间前写的。实际上应用另类拉格朗日反演的幂级数形式可以减少一点点细节的讨论（并没有减小多少）。
代码：
1 |
|