前言
GPT 时代感觉多项式题正在失去存在意义，因此撰写这篇文章整理了一些我之前考虑过并由 GPT 完善的多项式技术，基本以题目的形式呈现。
事实上就是把自己以前的 idea 用 GPT 改善一遍顺便发出来。
网格图完美匹配计数
简要题意
给定 $n\times m$ 的网格图，顶点为 $(i,j)$（$1\le i\le n$，$1\le j\le m$），曼哈顿距离为 $1$ 的两个顶点之间连边，求完美匹配数模 $998244353$。保证 $2\mid nm$，$1\le n\le 10^9$，$1\le m\le 5\times 10^4$。
相关题目：Timus 1594 Aztec Treasure，两边长度均不超过 $100$，模数为 $10^9+7$；QOJ 2447 Domino Covering，短边不超过 $35$，长边不超过 $10^{18}$，模数为输入的素数。
简要题解
记 $r_s(j)=2\cos\frac{j\pi}{s+1}$，$a=\lfloor n/2\rfloor$，$b=\lfloor m/2\rfloor$。由经典的 Kasteleyn–Temperley–Fisher 公式，完美匹配数为
$$ D_{n,m}=\prod_{j=1}^{b}\prod_{k=1}^{a}\bigl(r_m(j)^2+r_n(k)^2\bigr). $$
若某一维为奇数，经典公式还包含零根对应的因子；另一维为偶数，而 $\prod_{j=1}^{s/2}r_s(j)^2=1$（$s$ 为偶数），所以这些因子可以省略。
令 $F_s(x)=U_s(x/2)$，其中 $U_s$ 是第二类 Chebyshev 多项式，则
$$ F_s(x)=\prod_{j=1}^s(x-r_s(j)) =\sum_{t=0}^{\lfloor s/2\rfloor}(-1)^t\binom{s-t}{t}x^{s-2t}. $$
将正负成对的根合并，定义首一整系数多项式
$$ H_s(y)=\prod_{j=1}^{\lfloor s/2\rfloor}(y-r_s(j)^2), \qquad F_s(x)=x^{s\bmod 2}H_s(x^2). $$
于是答案可以写成结式
$$ D_{n,m}=(-1)^{ab}\operatorname{res}\bigl(H_m(y),H_n(-y)\bigr). $$
其中 $(-1)^{ab}$ 来自 $H_n(-y)=(-1)^a\prod_{k=1}^a(y+r_n(k)^2)$。这是整系数恒等式，可以直接模 $998244353$ 计算。
$H_m$ 的系数可以从 $F_m$ 的系数公式中 $O(m)$ 求出。由于 $H_m$ 首一，只需求 $H_n(-y)\bmod H_m(y)$，再计算结式。固定 $\varepsilon\in\{0,1\}$，令 $A_t(y)=H_{2t+\varepsilon}(y)$，由 Chebyshev 多项式的递推关系可得
$$ A_0=1,\qquad A_1=y-(1+\varepsilon),\qquad A_t=(y-2)A_{t-1}-A_{t-2}\quad(t\ge2). $$
取 $\varepsilon=n\bmod2$，将 $y$ 换成 $-y$，在模 $H_m$ 的商环中对递推矩阵快速幂，即可 $O(m\log m\log n)$ 求出余式。最后用折半 Euclid 算法 $O(m\log^2m)$ 求结式，总复杂度为 $O(m\log m(\log n+\log m))$。$m=1$ 时单独返回 $1$。
关于经典乘积公式及结式的联系，可参见 Counting Domino Tilings of Rectangles via Resultants。
同色连通块赋权的树计数
简要题意
给定 $m$ 种颜色及系数 $c_1,c_2,\dots,c_N$。对于一棵点带颜色的标号无根树，设其所有极大同色连通块为 $C_1,\dots,C_t$，定义权值为 $\prod_{i=1}^t c_{|C_i|}$。对每个 $1\le n\le N$，求所有 $n$ 个点的这类树的权值之和。
答案模 $998244353$，$N\le10^5$，$1\le m<998244353$，$0\le c_j<998244353$。取 $c_j=[j\le k]$ 即为限制同色连通块大小不超过 $k$ 的情形。
简要题解
先计数有根树。令 $F(x)$ 为有根颜色树的带权 EGF，并令
$$ G(x)=\sum_{j=1}^N c_j\frac{j^{j-1}}{j!}x^j. $$
按根所在的极大同色连通块分解：大小为 $j$ 的块内有 $j^{j-1}$ 种有根标号树，带权 $c_j$，整块有 $m$ 种颜色；每个点可以挂任意多棵根颜色不同的子树，权值相乘。因此
$$ F(x)=mG\left(x\exp\left(\frac{m-1}{m}F(x)\right)\right). $$
设 $A=F/m$，$d=m-1$，则 $A=G(x\mathrm e^{dA})$。引入 $B=x\mathrm e^{dA}$，有
$$ B=x\mathrm e^{dG(B)},\qquad B\mathrm e^{-dG(B)}=x. $$
记 $Q(x)=x\mathrm e^{-dG(x)}$，用 $Q^{\langle-1\rangle}$ 表示复合逆，则
$$ B=Q^{\langle-1\rangle},\qquad A=\frac1d\log\frac{B(x)}x\quad(d\ne0). $$
$Q$ 的一次项系数恒为 $1$，所以即使 $c_1=0$，复合逆仍然存在。这样只需求一次多项式指数、一次复合逆和一次对数，无须实际计算 $G(B)$。为求出 $A$ 到 $x^N$，需要将 $Q$ 和 $B$ 算到 $x^{N+1}$。使用二元 Bostan–Mori 实现复合逆，总复杂度 $O(N\log^2N)$，最后答案为 $m(n-1)![x^n]A(x)$。$m=1$ 时单独处理，此时 $A=G$，答案就是 $c_n n^{n-2}$（$n=1$ 时为 $c_1$）。
具体地，当 $G(0)=0$、$G'(0)\ne0$ 时，对任意给定的 $R$，不必先求复合逆再复合，可以直接用一次二元 Bostan–Mori 求出 $R\circ G^{\langle-1\rangle}$。由 Lagrange 反演，对 $1\le j\le N$ 有
$$ \begin{aligned} [x^j]R\bigl(G^{\langle-1\rangle}(x)\bigr) &=\frac1j[t^{j-1}]R'(t)\left(\frac{t}{G(t)}\right)^j\\ &=\frac1j[t^{N-1}]R'(t)\left(\frac{t}{G(t)}\right)^N G(t)^{N-j}. \end{aligned} $$
因此只需批量求 $[t^{N-1}]S(t)G(t)^\ell$（$0\le\ell<N$），也就是求二元有理式 $S(t)/(1-uG(t))$ 的 $[t^{N-1}]$，其中 $S=R'(t)(t/G(t))^N$，常数项另取 $R(0)$。这同样可以在 $O(N\log^2N)$ 内完成，取 $R(x)=x$ 就是复合逆的情形。
按重数赋权的异或零多重集计数
简要题意
给定 $R=\sum_{i=1}^m2^{a_i}$，其中 $0\le a_1<\cdots<a_m$，以及系数 $b_1,b_2,\dots,b_n$。从 $[0,R)$ 中选出一个大小为 $n$、所有元素的异或和为 $0$ 的多重集。若其中不同的数分别出现了 $k_1,\dots,k_\ell$ 次，定义权值为 $\prod_{i=1}^{\ell}b_{k_i}$，求所有这类多重集的权值之和模 $998244353$。
两种方案仅按各个数的出现次数区分，未出现的数贡献权值 $1$。$1\le n,m\le10^5$，$a_m\le10^{18}$，$0\le b_k<998244353$。
相关题目：QOJ 13267，序列 $b_k$ 仅有 $c$ 项非零。最初出在联考，后来搬到 QOJ。出题时尚在前 $\log^2$ 复合时代，因此加了 $c$ 的限制。
简要题解
令 $f(t)=1+\sum_{k=1}^n b_kt^k$，取 $L=a_m+1$，并记 $\chi_T(S)=(-1)^{\operatorname{popcount}(S\mathbin{\&}T)}$。由异或 FWT，答案为
$$ 2^{-L}[t^n]\sum_{T=0}^{2^L-1}\prod_{S=0}^{R-1}f(\chi_T(S)t). $$
令 $w_T=\sum_{S=0}^{R-1}\chi_T(S)$，则乘积中正号和负号的个数分别为 $(R+w_T)/2$ 和 $(R-w_T)/2$。定义
$$ E(t)=\exp\left(\frac R2\bigl(\log f(t)+\log f(-t)\bigr)\right),\qquad J(t)=\frac{\log f(t)-\log f(-t)}2, $$
答案就变成 $2^{-L}\sum_T[t^n]E(t)\mathrm e^{w_TJ(t)}$。
首先压缩 $w_T$ 的分布。对于 $T\ne0$，设其最低的非零位为 $h$。将 $[0,R)$ 按 $R$ 的二进制位拆成对齐的块：大小超过 $2^h$ 的块内正负抵消，其余块内符号相同或相反。因此，记 $r_h=R\bmod2^h$，有
$$ v_h=\begin{cases} 2^h-r_h,&R\text{ 的第 }h\text{ 位为 }1,\\ r_h,&R\text{ 的第 }h\text{ 位为 }0. \end{cases} $$
当 $h<a_m$ 时，更高位中至少有一个 $R$ 的非零位，使得 $w_T=\pm v_h$ 各占一半；计入 $2^{-L}$ 后，两者的权重均为 $2^{-h-2}$。当 $h=a_m$ 时只有一个 $T$，其值为 $2^{a_m}-\sum_{i<m}2^{a_i}$，权重为 $2^{-L}$；另外 $T=0$ 对应 $w_T=R$，权重同样为 $2^{-L}$。
在相邻的非零位之间，$v_h$ 不变，权重可以用等比数列求和。因此只需保留 $O(m)$ 对数值与权重 $(w_i,\lambda_i)$，无需枚举全部位。所有数值和权重均可直接在模意义下计算。
接下来令
$$ P(u)=[t^n]E(t)\mathrm e^{uJ(t)} =\sum_{j=0}^n p_ju^j,\qquad p_j=\frac1{j!}[t^n]E(t)J(t)^j. $$
因为 $J(0)=0$，这些系数可以用一次二元 Bostan–Mori，从
$$ [t^n]\frac{E(t)}{1-uJ(t)} $$
中批量提取，再逐项除以 $j!$。这里不要求 $J$ 的一次项非零，因此也允许 $b_1=0$。另一方面，带权幂和 $s_j=\sum_i\lambda_iw_i^j$ 的生成函数为
$$ \sum_{j\ge0}s_jz^j=\sum_i\frac{\lambda_i}{1-w_iz}. $$
用分治合并分式，再求逆展开到 $z^n$，即可得到 $s_0,\dots,s_n$。最终答案为 $\sum_{j=0}^n p_js_j$。
使用普通乘积树合并分式，上述实现的总复杂度为 $O\bigl(m\log(a_m+2)+(n+m)\log^2(n+m)\bigr)$；前一项来自计算稀疏二进制位对应的模幂。系数 $b_k$ 可以任意给定，不要求非零项稀疏。
连续段长度受限的排列计数
简要题意
称排列中位置连续且值域连续的一段为连续段。给定 $1\le m<n\le10^5$，计数不存在长度为 $m+1,\dots,n-1$ 的连续段的 $n$ 元排列，答案模 $998244353$。
相关题目：洛谷 P7278 纯洁憧憬、牛客比赛 38727 的 I 题、QOJ 4822 Matrix Counting，三题都是我出的，但出后两题时只做到了 $O(n\log^2 n/\log\log n)$。
简要题解
先用析合树把组合部分化简。记
$$ P(x)=\sum_{j\ge1}j!x^j,\qquad H(x)=\sum_{j=1}^m j!x^j, $$
并令 $S(x)$ 为长度至少为 $4$ 的单排列的 OGF。按照根为叶子、合点、析点分类，有
$$ P=x+\frac{2P^2}{1+P}+S(P), $$
故令 $Y=P^{\langle-1\rangle}(H)$，便有
$$ S(H)=H-\frac{2H^2}{1+H}-Y. $$
根为析点时，所有真连续段都包含在某个儿子中，故只需限制每个儿子的大小不超过 $m$，贡献就是 $[x^n]S(H)$。
根为合点时，按固定方向的直和不可分块唯一拆分。每块的 OGF 为 $I=P/(1+P)$，相邻若干整块的并也是连续段。因而条件等价于首尾两块的大小均至少为 $n-m$，每块的大小均不超过 $m$。令
$$ J(x)=\sum_{j=n-m}^m[x^j]I(x)\,x^j, $$
则这部分的贡献为 $2[x^n](1+P)J^2$：中间任意多块的 OGF 为 $1/(1-I)=1+P$；首尾的下界已保证中间总大小至多为 $2m-n<m$，因此不必再截断中间部分。于是答案为
$$ \boxed{[x^n]\left(H-\frac{2H^2}{1+H}-Y+2(1+P)J^2\right).} $$
组合部分也可参见原比赛题解。剩下的关键是用 $O(n\log n)$ 计算 $Y$，而不是真的先求复合逆再复合。
由阶乘的递推，$P$ 满足
$$ x^2P'(x)+(x-1)P(x)+x=0. $$
将 $P(Y)=H$ 代入，利用 $P'(Y)Y'=H'$，得到
$$ \Phi(Y):=Y^2H'+\bigl((1+H)Y-H\bigr)Y'=0. $$
对这个方程做 Newton 迭代。设当前近似为 $y$，修正量为 $h$，则需求解
$$ Bh'+Ch=-\Phi(y),\qquad B=(1+H)y-H,\quad C=2yH'+(1+H)y'. $$
从 $y=x+([x^2]H-2)x^2$ 开始，始终有 $B=-x^2+O(x^3)$、$C=1+O(x)$。除以单位 $B/x^2$ 后，归结为
$$ x^2h'+a(x)h=r(x),\qquad a(0)\ne0. $$
直接套积分因子会出现 $\exp(c/x)$，无法在形式 Laurent 级数中运算。但只需消去 $a$ 的二次及以上部分：写成
$$ a=a_0+a_1x+x^2q(x),\qquad U=\exp\left(-\int q(x)\,\mathrm dx\right),\qquad h=Uz, $$
原方程就变为
$$ x^2z'+(a_0+a_1x)z=r/U. $$
记 $s=r/U$，比较系数得到
$$ z_k=\frac{s_k-(a_1+k-1)z_{k-1}}{a_0},\qquad z_{-1}=0. $$
这部分可以线性递推，前后的多项式求逆、指数与乘法都是 $O(M(n))$，所以一次线性化方程的求解只需 $O(M(n))$。
最后检查精度：若 $y-Y=O(x^k)$，则 $h=O(x^k)$，更新后的非线性余项为
$$ \Phi(y+h)-\Phi(y)-Bh'-Ch =H'h^2+(1+H)hh'=O(x^{2k-1}). $$
线性算子保持最低非零项的次数，故精度从 $k$ 提升到 $2k-1$。按 $3,5,9,17,\dots$ 倍增，总复杂度为 $O(M(n))=O(n\log n)$。其余组合部分只涉及常数次求逆和乘法，整个问题同样是 $O(n\log n)$。
同时求出所有长度的答案
如果固定 $m$，要求同时计算 $n=m+1,\dots,N$ 的答案，析点部分只需将 $Y$ 和相应的有理式一次算到 $x^N$，复杂度仍为 $O(N\log N)$。合点部分的截断下界随 $n$ 变化，需要另外处理。
记 $I_j=[x^j]I(x)$，并暂时去掉正反两个方向的系数 $2$，令
$$ C_n=[x^n](1+P)\left(\sum_{j=n-m}^m I_jx^j\right)^2. $$
当 $n>2m$ 时 $C_n=0$。对于 $m<n\le2m$，令 $t=2m-n$、$a_i=I_{m-i}$（$0\le i<m$），展开可得
$$ C_{2m-t}=\sum_{\substack{0\le i,j\le t\\i+j\ge t}}a_i a_j(i+j-t)!. $$
令 $k=i+j-t$，条件恰好变成 $0\le k\le\min(i,j)$。因此定义后缀平方和
$$ T(x)=\sum_{k=0}^{m-1}k!x^k \left(\sum_{i=k}^{m-1}a_i x^{i-k}\right)^2, $$
就有 $C_{2m-t}=[x^t]T(x)$，只需求出 $T\bmod x^m$。
这个式子可以分治计算。考虑指标都在 $[l,r)$ 内的三元组 $(k,i,j)$，其贡献为 $k!a_i a_jx^{i+j-k}$，且 $k\le i,j$。令中点为 $b$，全部位于同一半的三元组递归处理；跨越中点时，必有 $k<b$，并且至少一个端点在右半。
具体地，设
$$ R(x)=\sum_{i=b}^{r-1}a_i x^{i-b},\qquad W(x)=\sum_{k=l}^{b-1}k!x^{b-1-k},\qquad F(x)=\sum_{s=0}^{b-l-1}\left(\sum_{k=l}^{b-1-s}k!a_{k+s}\right)x^s. $$
$F$ 可由左半序列与反转后的阶乘序列卷积得到。一个端点在右半、另一个在左半时，贡献为 $2x^bR(x)F(x)$；两个端点都在右半时，贡献为 $x^{b+1}R(x)^2W(x)$。每层只需常数次卷积，故这部分的复杂度为 $O(M(m)\log m)=O(m\log^2m)$。
最后对每个 $n$ 输出 $[x^n]S(H)+2C_n$。总复杂度为
$$ \boxed{O(N\log N+m\log^2m),} $$
循环群自由积中的有限阶字计数
简要题意
给定 $m$ 种字符，第 $i$ 种恰有 $n_i$ 个，每个字符可以选择 $c_i$ 种颜色。允许删除连续的 $d_i$ 个同种同色字符。给定正整数 $k$，求有多少个字符串 $S$，使得将它重复拼接 $k$ 次得到的 $S^k$ 可以消为空串。答案模 $998244353$。
$1\le n_i,d_i\le10^8$、$1\le c_i<998244353$，且 $\sum_i\lceil n_i/d_i\rceil\le2\cdot10^5$。
相关题目：CF2223F Zhily and Colorful Strings，只要求 $S$ 消为空串，即 $k=1$。
简要题解
以下组合部分（由 GPT）在抽象代数语言下解释，出题时笔者从原来的形式得到了一样的结论，但没有得到最后的算法。
给第 $i$ 种字符的第 $j$ 种颜色分配一个生成元 $a_{i,j}$，考虑群
$$ \Gamma=\mathop{*}_{i=1}^m\mathop{*}_{j=1}^{c_i}C_{d_i} =\left\langle a_{i,j}\mid a_{i,j}^{d_i}=1\right\rangle. $$
这里 $*$ 表示自由积，不要求不同生成元交换。每个字符串是这些生成元组成的一个正字，空串对应单位元。相邻的同一生成元合并指数，再将指数对 $d_i$ 取模，就是自由积的正规形归约。因此，字符串能消为空，当且仅当它代表单位元。题目计数的是具有指定各类字母数的字，而不是不同的群元素。
原始条件便是
$$ [S]^k=1\quad\text{于 }\Gamma. $$
自由积的有限阶元素都共轭于某个因子中的元素。这里可以直接看出：将一个元素共轭化为循环约化的正规形，若其音节数至少为 $2$，则首尾来自不同因子，重复拼接不会约去任何音节，因而不可能有有限阶。所以除了单位元，只需考虑
$$ [S]=v a_{p,j}^{r_p}v^{-1},\qquad 1\le r_p<d_p,\qquad d_p\mid kr_p. $$
要求 $v$ 的最后一个音节不来自 $\langle a_{p,j}\rangle$，便得到唯一的这种共轭正规形。其阶为 $d_p/\gcd(d_p,r_p)$。
写 $n_i=b_id_i+r_i$，其中 $0\le r_i<d_i$。将群映到 $\prod_i C_{d_i}$，令同一种字符的所有颜色映到同一个生成元，可以看出：至多允许一个 $r_p>0$；若存在这样的 $p$，还必须有 $d_p\mid kr_p$。若所有 $r_i=0$，满足要求的字只能代表单位元。以下分别计数这两种情况。
单位元的字。 自由积的 Cayley 图由各生成元对应的有向 $d_i$ 边形连接而成，不同边形之间具有树状结构。将闭路按首次返回分解：以颜色 $(i,j)$ 出发的一次首次返回，需要沿对应的边形走满 $d_i$ 步，在中间的 $d_i-1$ 个顶点处插入若干次闭路；这些闭路不能以同一个生成元出发，否则应当继续沿当前边形前进，而不是另开一次返回。这也给出了正规形栈所确定的唯一嵌套结构。$d_i=1$ 时，对应一条自环，没有内部插槽。
每走满一个第 $i$ 类边形消耗 $d_i$ 个字符。先提出颜色因子 $\mathbf c^{\mathbf b}=\prod_i c_i^{b_i}$，记 $q_i=1/c_i$，令 $F_i(\mathbf x)$ 记录根为第 $i$ 类首次返回的结构，其权为各边形独立选色后符合限制的概率。父子同类时颜色相同的概率为 $q_i$，故
$$ F_i=\frac{x_i}{(1-\sum_jF_j+q_iF_i)^{d_i-1}} =x_iG_i(\mathbf F),\qquad G_i(\mathbf x)=\frac1{(1-\sum_jx_j+q_ix_i)^{d_i-1}}. $$
任意闭路是首次返回的有序序列，所以令
$$ H(\mathbf x)=\frac1{1-\sum_i x_i}, $$
所求为 $\mathbf c^{\mathbf b}[\mathbf x^{\mathbf b}]H(\mathbf F)$。由多元 Lagrange 反演，
$$ [\mathbf x^{\mathbf b}]H(\mathbf F) =[\mathbf x^{\mathbf b}]H(\mathbf x)\mathbf G(\mathbf x)^{\mathbf b} \det\left([i=j]-\frac{x_j}{G_i}\frac{\partial G_i}{\partial x_j}\right). $$
令 $t_i=x_i/(1-\sum_jx_j)$，将公共的 $1-\sum_jx_j$ 因子提出，得到
$$ [\mathbf x^{\mathbf b}] \frac{P(\mathbf t)}{(1-\sum_jx_j)^{1+\sum_i b_i(d_i-1)}}. $$
这里 $P$ 包含 $\mathbf G^{\mathbf b}$ 中剩余的因子和行列式。该行列式是对角矩阵减去秩一矩阵，因此
$$ \begin{aligned} P(\mathbf t) &=\prod_i\frac1{(1+q_it_i)^{b_i(d_i-1)+1}} \det\left([i=j](1+d_iq_it_i)-(d_i-1)t_j\right)\\ &=\left(1-\sum_i\frac{(d_i-1)t_i}{1+d_iq_it_i}\right) \prod_i\frac{1+d_iq_it_i}{(1+q_it_i)^{b_i(d_i-1)+1}}\\ &=[u^1](1+u)\prod_i \frac{1+d_iq_it_i-(d_i-1)ut_i}{(1+q_it_i)^{b_i(d_i-1)+1}}. \end{aligned} $$
记 $K=\sum_i b_i$、$N=\sum_i n_i$。$P$ 中单项式 $\mathbf t^{\mathbf e}$ 对应的系数提取为
$$ [\mathbf x^{\mathbf b-\mathbf e}] (1-\sum_i x_i)^{-1-N+K-\sum_i e_i} =\frac{N!}{(N-K+\sum_i e_i)!}\prod_i\frac1{(b_i-e_i)!}. $$
因此只需用 $w$ 记录 $\sum_i e_i$，定义
$$ \operatorname{Poly}_i(w,u)=\sum_{e=0}^{b_i}\frac{w^e}{(b_i-e)!} [t_i^e]\frac{1+d_iq_it_i-(d_i-1)ut_i}{(1+q_it_i)^{b_i(d_i-1)+1}}, $$
则单位元部分的答案为
$$ \boxed{\mathbf c^{\mathbf b}\sum_{s=0}^K \frac{N!}{(N-K+s)!}[w^s u^1](1+u)\prod_i\operatorname{Poly}_i(w,u).} $$
非平凡有限阶元素的字。 接下来设恰有一个 $r_p>0$，且 $d_p\mid kr_p$。这时需要计数共轭于 $a_{p,j}^{r_p}$ 的字，并枚举核心颜色 $j$。
沿共轭正规形 $v a_{p,j}^{r_p}v^{-1}$ 看，一个第 $i$ 类音节 $a_{i,j}^s$ 与逆音节 $a_{i,j}^{d_i-s}$ 配对，合计消耗 $d_i$ 个字符，并有 $d_i-1$ 种选择 $s$ 的方式。于是整个结构是一条共轭链，最内层是 $r_p$ 个核心字符，各处附着前面计数的闭路。
暂记 $A_i=1-\sum_jF_j+q_iF_i$。每层除去通向下一层的插槽，还需计入返回后的闭路，其权为
$$ \frac{(d_i-1)x_i}{A_i^{d_i}} =\frac{(d_i-1)F_i}{A_i}. $$
共轭正规形要求相邻音节不属于同一个循环因子，最内层音节也不能属于核心因子。对加权序列禁止相邻同色，可用连续同色段的容斥：若第 $i$ 类一层的权为 $L_i$，便将它替换为 $L_i/(1+q_iL_i)$；若末端还禁止指定的第 $p$ 类颜色，再乘 $1/(1+q_pL_p)$。这里仅禁止同种且同色，同种不同色仍属于不同的自由因子。
代入 $L_i=(d_i-1)F_i/A_i$，再补上链开始前的任意闭路和核心处的 $r_p$ 个插槽，得到归一化生成函数
$$ \frac1{1-\sum_iF_i} \frac1{1-\sum_i\frac{(d_i-1)F_i}{1-\sum_jF_j+q_id_iF_i}} \frac1{1+\frac{q_p(d_p-1)F_p}{A_p}} \frac1{A_p^{r_p}}. $$
最终还需乘 $c_p\mathbf c^{\mathbf b}$，其中 $c_p$ 来自核心的颜色选择。对上式同样做多元 Lagrange 反演，所得系数形如
$$ [\mathbf x^{\mathbf b}] \frac{Q(\mathbf t)}{(1-\sum_jx_j)^{1+\sum_i b_i(d_i-1)+r_p}}, $$
其中
$$ Q(\mathbf t)= \frac{P(\mathbf t)} {\left(1-\sum_i\frac{(d_i-1)t_i}{1+q_id_it_i}\right) (1+q_pd_pt_p)(1+q_pt_p)^{r_p-1}}. $$
此处共轭链贡献的分母，恰好与 $P$ 的秩一行列式因子约去，核心对应的 $1+d_pq_pt_p$ 也被约去。因此实际上
$$ \boxed{Q(\mathbf t)= \frac1{(1+q_pt_p)^{b_p(d_p-1)+r_p}} \prod_{i\ne p}\frac{1+d_iq_it_i}{(1+q_it_i)^{b_i(d_i-1)+1}}.} $$
这比单位元情形还简单，已经完全分离变量，不需要增加新的形式元。将右侧第 $i$ 个单变量因子记作 $Q_i(t_i)$，令
$$ \operatorname{Poly}_i(w)=\sum_{e=0}^{b_i} \frac{w^e}{(b_i-e)!}[t_i^e]Q_i(t_i), $$
即可得到原始 idea 中非平凡有限阶元素部分的答案
$$ \boxed{c_p\mathbf c^{\mathbf b}\sum_{s=0}^K \frac{N!}{(N-K+s)!}[w^s]\prod_i\operatorname{Poly}_i(w).} $$
两种情况的每个单变量因子都可用二项式展开在线性时间内构造，再分治相乘。单位元情形只需保留 $u$ 的零次、一次项，故总复杂度均为 $O(K\log^2(K+2)+m\log 998244353)$，后一项用于颜色的求逆、幂运算；非平凡核心情形也允许 $K=0$，此时答案就是 $c_p$。
注意 $N$ 可能超过模数，式中的阶乘比值应理解为长度为 $K-s$ 的下降阶乘
$$ \frac{N!}{(N-K+s)!}=\prod_{j=N-K+s+1}^{N}j, $$
不能直接对大阶乘求逆。所有 $s$ 的值可倒序递推；真正需要求逆的阶乘下标只有 $0,\dots,K$。这样，$k$ 的作用仅是判断核心元素的阶是否整除它，并不会放大多项式的规模。
