pjudge cts 比赛，什么都不会暴力也打不出啥，自闭了。下午做一些杂题回一回神吧，可能不太算杂题因为你发现大部分都是 Poly。
UOJ424 集训队作业2018 count
同构等价于笛卡尔树同构，而所有的数都出现过的要求是不必要的（因为可以等价成一个 \([1,m]\) 都出现的序列）。那么考虑对笛卡尔树的形态计数，要求值域在 \([1,m]\) 的范围内等价于左链长度不大于 \(m-1\)。就相当于一个长度为 \(2n\) 的括号序列，要求任意时刻 ( 的数量减去 ) 的数量不超过 \(m\)，这可以用折线法计数，具体参照骗我呢那题。
但其实我们也可以 dp，设 \(f[i,j]\) 代表 \(i\) 个点，最长左链+1不超过 \(j\) 的方案数。\(f_{0,0}=1,f_{i,1}=1\)。转移方程考虑二叉树的合并，\(f_{i,j}=\sum_{k=0}^{i-1}f_{k,j-1}\times f_{n-1-k,j}\)，这是一个卷积的形式，设 \(F_i\) 是 \(f_{*,i}\) 的 OGF，\(F_i=xF_{i-1}F_{i}+1,F_i=\frac{1}{1-xF_{i-1}}\)。
直接暴力 NTT 是 \(O(nm\log n)\) 的，但是学过数列的都知道这个可以写成通项，是矩阵次幂的形式，于是可以矩阵快速幂 \(O(n\log n\log m)\)。DFT 是线性变换，所以可以先变成点值，然后用点值矩阵乘法再 IDFT 回去，复杂度 \(O(n\log m)\)。
ABC260Ex Colorfulness
先转换为计数恰好有 \(n\) 个不同相邻小球的方案数记为 \(g_n\)。然后答案就很好算了 \(f_k=\sum\limits_{i=0}^{N-1}i^kg_i\)，将其看做生成函数，有 \(F(n)=\sum _{k\ge 0}\sum\limits_{i=0}^{N-1}i^kg_ix^k=\sum\limits_{i=0}^{N-1}g_i\sum_{k\ge 0}i^kx^k=\sum\limits_{i=0}^{N-1}\frac{g_i}{1-kx}\)。这个东西呢是可以分治 ntt 然后复杂度就是 \(O(n\log^2n)\)。
接下来考虑如何计算 \(g_n\)。