做題筆記11

7.23

P6192 【模板】最小斯坦納樹

發現這個連通圖肯定是原圖上一顆生成樹，考慮 dp，記 $dp(i,S)$ 為樹根是 $i$，$k$ 中的點考慮了 $S$ 個，那么有轉移：

$dp(i,S)+w(i,j)\rightarrow dp(j,S)$，把 $i$ 踢掉并把根換成 $j$
$dp(i,T)+dp(i,S/T)\rightarrow dp(i,S)$，把 $i$ 兩邊的子樹合并起來

第一種轉移直接最短路，第二種轉移枚舉子集 dp 即可，復雜度 $\mathcal{O}(n3^k+m\log m2^k)$

7.24

模擬賽

T1

隨便嗯的一點五次

T2

打表。

T3

考慮 op=1，發現他兩邊的貢獻是獨立的，于是記 $f_i$ 為長度為 $i+1$ 的段，$(i,i)$ 這個節點的期望深度，則有 $f_i=1+\frac{1}{i}\sum\limits_{j<i}f_j$，答案就是 $f_{x-1}+f_{n-x}+1$

當 op=2 時，當 $l=1$ 時，答案就是 $f_{r}\times 2+f_{n-r}-1$，這里會乘二再減一是因為線段樹上父節點左兒子和右兒子都會遍歷到，當 $r=n$ 時，由于情況是對稱的，答案就是 $f_{n-l+1}\times 2+f_{l-1}-1$

如果 $l\ne 1$ 且 $r\ne n$，可以枚舉每一個中點 $k$，這樣可以變成一邊 $l=1$ 和一邊 $r=n$ 的情況，答案就是 $f_{l-1}+f_{n-r}+\sum\limits_{k=0}^{r-l+1}2\times f_{k}+2\times f_{r-l+1-k}-1$，中間那個和式根據我們對 $f$ 的定義，發現就是 $4\times f_{r-l+2}$，于是這樣我們就可以 $\mathcal{O}(n)$ 預處理 $\mathcal{O}(1)$ 詢問答案了

P7329 「MCOI-07」Dream and More Discs

最幽默的一集

所有的東西掛在一起二分，這時候把 $a_{i,mid_i}$ 排序，同時記 $c=\sum\limits mid_i$，如果 $c\ge k$，我們肯定是讓最大的那個往左縮，接著遞歸子問題，否則把最小的往右縮，遞歸子問題

P10664 BZOJ3328 PYXFIB

看看單看看位看看根看看反看看演

求

\[ \sum_{i=0}^{\left\lfloor\frac{n}{k}\right\rfloor}\binom{n}{i\times k}\text{Fib}_{i\times k} \]

原式就等于

\[ \sum\limits_{i=0}^{n}[k|i]\binom{n}{i}\text{Fib}_i \]

反反的演：

\[\begin{align} & \sum\limits_{i=0}^{n}[k|i]\binom{n}{i}\text{Fib}_i\\ & =\sum_{i=0}^n\frac{1}{k}\sum_{j=0}^{k-1}\omega_{k}^{ij}\binom{n}{i}\text{Fib}_i\\ \end{align} \]

考慮 $$Fib_i=\begin{bmatrix}
1& 1\
1 &0
\end{bmatrix}^i$$
記這個矩陣為 $G$，那么原式就是

\[\begin{align} & \sum_{i=0}^n\frac{1}{k}\sum_{j=0}^{k-1}\omega_{k}^{ij}\binom{n}{i}G^i\\ & = \frac{1}{k}\sum_{j=0}^{k-1}\sum_{i=0}^{n}\binom{n}{i}(\omega_{k}^{j}G)^i\\ & = \frac{1}{k}\sum_{j=0}^{k-1}(I+\omega_{k}^{j}G)^n\\ \end{align}\]

這里能二項式定理是因為 $I$ 和任何矩陣的乘法都是滿足交換律的，取 $\omega_{k}=g^{\frac{p-1}{k}}$ 即可，其中 $g$ 是 $p$ 的一個原根，最后復雜度大概是 $\mathcal{O}(k\log n)$ 再加上找原根的復雜度

P5591 小豬佩奇學數學

推式子。

$k$ 比較小，考慮單位根反演

\[\begin{align} & \sum_{i=0}^{n}\binom{n}{i}p^i\left\lfloor \frac{i}{k}\right\rfloor \\ & =\sum_{i=0}^n\binom{n}{i}p^i\left(\sum_{j=0}^{i}[k|j]-1 \right)\\ & = \sum_{i=0}^n\binom{n}{i}p^i\sum_{j=0}^{i}[k|j]-(1+p)^n\\ & = \sum_{i=0}^n\binom{n}{i}p^i\sum_{j=0}^{i}\frac{1}{k}\sum_{l=0}^{k-1}\omega_{k}^{lj}-(1+p)^n\\ & = \frac{1}{k}\sum_{l=0}^{k-1}\sum_{i=0}^n\binom{n}{i}p^i\sum_{j=0}^{i}\omega_{k}^{lj}-(1+p)^n\\ & = \frac{1}{k}\sum_{l=0}^{k-1}\sum_{i=0}^n\binom{n}{i}p^i\frac{\omega_{k}^{l(i+1)}-1}{\omega_{k}^{l}-1}-(1+p)^n\\ & = \frac{1}{k}\sum\limits_{l=0}^{k-1}\frac{\sum\limits_{i=0}^n\binom{n}{i}p^i\omega_{k}^{l(i+1)}-1}{\omega_{k}^{l}-1}-(1+p)^n\\ & = \frac{1}{k}\sum\limits_{l=0}^{k-1}\frac{\omega_{k}^l\sum\limits_{i=0}^n\binom{n}{i}(p\omega_{k}^{l})^i-(1+p)^n}{\omega_{k}^{l}-1}-(1+p)^n\\ & = \frac{1}{k}\sum\limits_{l=0}^{k-1}\frac{\omega_{k}^l(1+p\omega_{k}^{l})^n-(1+p)^n}{\omega_{k}^{l}-1}-(1+p)^n\\ \end{align} \]

發現當 $l=0$ 的時候會除以 $0$，單獨算一下：

\[ \begin{align} & \frac{1}{k}\sum_{i=0}^n\binom{n}{i}p^i\sum_{j=0}^{i}\omega_{k}^{lj}\\ & = \frac{1}{k}\sum_{i=0}^n\binom{n}{i}p^i(i+1)\\ & = \frac{1}{k}\sum_{i=0}^ni\binom{n}{i}p^i+\frac{1}{k}\sum_{i=0}^n\binom{n}{i}p^i\\ & = \frac{1}{k}np(1+p)^{n-1}+\frac{1}{k}(1+p)^n\\ \end{align} \]

這樣直接算就行了，復雜度 $\mathcal{O}(k\log n)$

7.25

n^2多項式操作博客（不是題）

P12230 集合冪級數 exp

板。

P12231 集合冪級數 ln

板。

P12232 集合冪級數求逆

板。

P10461 多項式復合集合冪級數

住店牛爹。

把集合冪級數 $F(S)$ 看作一個多元函數 $F(x_0,x_1,x_2,...,x_{n})$ 對 $x_0^2,x_1^2,...,x_n^2$ 同時取模的結果

求 $F=f(G)$，同時對 $x_n$ 求偏導，得 $\frac{\partial}{\partial x_n}F=\frac{\partial}{\partial x_n}G\frac{\partial f(z)}{\partial z}(G)$，考慮 $\frac{\partial}{\partial x_n}F$，有 $\frac{\partial}{\partial x_n}F=[x_n^1]F$，所以有 $[x^1_n]F=[x_n^1]G\frac{\partial f(z)}{\partial z}(G)$，后面的 $\frac{\partial f(z)}{\partial z}(G)$ 肯定只有 $x_n^0$ 處的系數有用，所以就有 $[x^1_n]F=[x_n^1]G[x_n^0]\frac{\partial f(z)}{\partial z}(G)$

重要結論：$[x^0_n]f(G)=f([x^0_n]G)$，因為只有 $0 \text{ or } 0$ 可能是 $0$，那么 $[x_n^1]$ 也就等于 $[x_n^1]G[x_n^0]\frac{\partial f(z)}{\partial z}([x_n^0]G)$

然后考慮 $[x_n^0]F$，此時 $[x_n^0]F=[x_n^0]f(G)=f([x_n^0]G)$

因為 $F=x_n^0[x_n^0]F+x_n^1[x_n^1]F$，于是我們可以遞歸兩邊，而兩邊的 $n$ 都減小了 $1$，最終復雜度就是 $\sum\limits_{i=0}^{n}(n-i)i^22^i=\mathcal{O}(n^22^n)$

P6620 [省選聯考 2020 A 卷] 組合數問題

隨便推獅子

\[\begin{align} & \sum_{k=0}^n\binom{n}{k}x^kf(k)\\ & = \sum_{k=0}^n\sum\limits_{i=0}^{m}a_ik^i\binom{n}{k}x^k\\ & = \sum\limits_{i=0}^{m}a_i\sum_{k=0}^nk^i\binom{n}{k}x^k\\ & = \sum\limits_{i=0}^{m}a_i\sum_{k=0}^n\sum_{l=0}^{i}\begin{Bmatrix}i\\l\end{Bmatrix}k^{\underline l}\binom{n}{k}x^k\\ & = \sum\limits_{i=0}^{m}a_i\sum_{k=0}^n\sum_{l=0}^{i}\begin{Bmatrix}i\\l\end{Bmatrix}\frac{k!}{(k-l)!}\frac{n!}{k!(n-k)!}x^k\\ & = \sum\limits_{i=0}^{m}a_i\sum_{k=0}^n\sum_{l=0}^{i}\begin{Bmatrix}i\\l\end{Bmatrix}n^{\underline l}\binom{n-l}{n-k}x^k\\ & = \sum\limits_{i=0}^{m}a_i\sum_{l=0}^{i}\begin{Bmatrix}i\\l\end{Bmatrix}n^{\underline l}\sum_{k=0}^n\binom{n-l}{n-k}x^k\\ & = \sum\limits_{i=0}^{m}a_i\sum_{l=0}^{i}\begin{Bmatrix}i\\l\end{Bmatrix}n^{\underline l}\sum_{k=l}^n\binom{n-l}{n-k}x^k\\ & = \sum\limits_{i=0}^{m}a_i\sum_{l=0}^{i}\begin{Bmatrix}i\\l\end{Bmatrix}n^{\underline l}x^l\sum_{k=0}^{n-l}\binom{n-l}{k}x^k\\ & = \sum\limits_{i=0}^{m}a_i\sum_{l=0}^{i}\begin{Bmatrix}i\\l\end{Bmatrix}n^{\underline l}x^l(1+x)^{n-l}\\ \end{align} \]

復雜度 $\mathcal{O}(m^2)$

P9168 [省選聯考 2023] 人員調度

唐題

暴力咋做？我們自底向上做，因為兒子子樹中選中的點在以后只會變少不會變多，我們維護出來這個被選中的點的集合 $S$，當我們到 $u$ 這個節點的時候，把這個節點的權值從大到小排序，考慮一個一個加進去，如果 $|S|<siz_u$，那么可以把這個權值隨便加進去，否則，只能是 $|S|=siz_u$，這意味著 $u$ 這個點的子樹已經滿了，我們可以反悔掉這個子樹中已經被選的權值最小的那個，把他踢掉，并把當前的權值加進去，一直做這個過程直到到了根即可，我們可以用一個可并堆維護，那單次復雜度就是 $\mathcal{O}(n^2\log n)$

如何優化？直接考慮沒有刪點操作，因為刪點的話可以線段樹分治，考慮加點的時候，如果其到根鏈上所有的節點的子樹都沒滿，那這個點可以直接放進去，否則，我們找到到根鏈上離他最近的已滿的節點，并嘗試反悔掉其子樹中權值最小的，而且我們發現只需要考慮這一個子樹，因為再往上的節點是滿足單調性的

于是我們要做的就是鏈加鏈 $\min$，單點修子樹 $\min$，用線段樹+樹剖直接維護即可，復雜度 $\mathcal{O}(n\log^2n)$，當然可以用全局平衡二叉樹等結構輕松做到單 $\log$

7.26

P4566 [CTSC2018] 青蕈領主

首先發現每一個區間不是相交就是包含，這個序列肯定構成一個樹形結構，對于這個樹上的節點 $u$，記其答案為 $dp_u$，那么有 $dp_u=?\times \prod_{v\in son(u)}dp_v$，記 $k$ 為 $u$ 的兒子個數，這個 $?$ 是否就是 $(k+1)!$，發現并非如此，因為我們在給兒子安排順序的時候，還要滿足他們都是極長的連續區間，也就是說如果相對大小相鄰的兩個兒子在樹上也相鄰，那這種安排權值的方案就是錯的，于是考慮 dp，$f(n)$ 表示不存在右端點在 $[1,n]$ 之間的連續區間的大小為 $n+1$ 的排列，那 $?$ 就是 $dp_k$，最終的答案就是 $\prod\limits_{i} f(k_i)$

現在要做的就是計算出 $f$ 的值，$f(n)$ 的含義是，所有的連續區間，要么包含最后一個元素，要么其大小為 $1$，其等價于，所有的連續區間，要么包含元素 $n+1$，要么大小為 $1$，現在再考慮去 dp $f$ 的值

考慮每次加進去一個最小值，那么有轉移 $f(n)=(n-1)f(n-1)+\sum\limits_{i=2}^{n-2}(n-i-1)f(i)f(n-i)$，第一個轉移，就是在一個長度為 $n-1$ 的合法序列中加入一個 $1$，可以發現加入之后必定也是合法的；第二個轉移則是對于原來就不合法的序列，我們加入一個 $1$ 使得其中本來的一個連續區間被斷開了，設其長度為 $l$，值域為 $[x,x+l-1]$，則肯定有 $x>1$，因為如果 $x=1$，這時候再插入一個最小值不會使得這個區間斷開，而又因為這個區間不經過最大值，就有 $x+l-1<n$，所以就有 $x\in[2,n-l]$，那共有 $n-l+1$ 種取值，對于這一段貢獻，其和外面的所有段的答案是 $f(n-l)$，其段內的答案是 $f(l)$，所以就能得出來后面的轉移了

分治卷積，對于 $[L,R]$，我們先算出 $[L,mid]$ 的 $f$ 的值，然后讓 $[2,R-L]\times [L,mid]$ 和 $[L,mid]\times[2,R-L]$ 貢獻到 $[mid+1,R]$ 就行了，復雜度是 $\mathcal{O}(n\log^2n)$

P6667 [清華集訓 2016] 如何優雅地求和

？？？？

令 $f(x)=\sum\limits_{i=0}^{x}\binom{x}{i}s_i$，二項式反演，就有 $s_x=\sum\limits_{i=0}^x\binom{x}{i}(-1)^{x-i}f(i)$，這樣我們把 $f$ 的點值轉成了一個帶組合數的式子！

開推。

\[ \begin{aligned} & \sum_{k=0}^nf(k)\binom{n}{k}x^k(1-x)^{n-k}\\ & = \sum_{k=0}^n\sum_{i=0}^{m}\binom{k}{i}\binom{n}{k}s_ix^k(1-x)^{n-k}\\ & = \sum_{i=0}^{m}s_i\sum_{k=i}^n\binom{k}{i}\binom{n}{k}x^k(1-x)^{n-k}\\ & = \sum_{i=0}^{m}s_i\sum_{k=i}^n\binom{k}{i}\binom{n}{k}x^k(1-x)^{n-k}\\ & = \sum_{i=0}^{m}s_i\sum_{k=i}^n\binom{n}{i}\binom{n-i}{k-i}x^k(1-x)^{n-k}\\ & = \sum_{i=0}^{m}\binom{n}{i}s_i\sum_{k=0}^{n-i}\binom{n-i}{k}x^{k+i}(1-x)^{n-k-i}\\ & = \sum_{i=0}^{m}\binom{n}{i}s_ix^i\sum_{k=0}^{n-i}\binom{n-i}{k}x^{k}(1-x)^{n-k-i}\\ & = \sum_{i=0}^{m}\binom{n}{i}s_ix^i(x+1-x)^{n-i}\\ & = \sum_{i=0}^{m}\binom{n}{i}s_ix^i\\ \end{aligned} \]

直接算就行了，復雜度 $\mathcal{O}(m\log m)$

Evaluation

考慮第 $k$ 項系數

\[ \begin{aligned} & \sum_{i=0}^{n-1}a_i(b\times c^{2k}+d)^i\\ & =\sum_{i=0}^{n-1}a_i\sum_{j=0}^{i}\binom{i}{j}(b\times c^{2k})^jd^{i-j}\\ & =\sum_{i=0}^{n-1}a_i\sum_{j=0}^{i}\binom{i}{j}d^{i-j}b^jc^{2jk}\\ & =\sum_{j=0}^{n-1}c^{2jk}\sum_{i=j}^{n-1}a_i\binom{i}{j}d^{i-j}b^j\\ \end{aligned} \]

記 $A_j=\sum\limits_{i=j}^{n-1}a_i\binom{i}{j}d^{i-j}b^j$，這是個卷積可以快速求，原式就

\[ \begin{aligned} & =\sum_{i=0}^{n-1}A_i\times c^{2ki}\\ & =\sum_{i=0}^{n-1}A_i\times c^{k^2+i^2-(k-i)^2}\\ & =c^{k^2}\sum_{i=0}^{n-1}A_i\times c^{i^2-(k-i)^2}\\ \end{aligned} \]

這樣就構造出來一個卷積了

CF958F3 Lightsabers (hard)

分治/哈夫曼樹直接卷就完了，需要 FFT

CF438E The Child and Binary Tree

記 $G(x)=\sum\limits_{c_i\in S}x^{c_i}$

求一個 $F(x)=(F(x)+1)(F(x)+1)G(x)$

可以直接解二次方程然后多項式開根求逆，當然也可以直接牛頓迭代

P5110 塊速遞推

這不是我們常系數齊次線性遞推嗎/wul，怎么火出圈了/wul，下次記得標明出處

P4451 [國家集訓隊] 整數的lqp拆分

\[ \sum_{i=0}^{\infty} F(x)^i \]

$F(x)$ 是斐波那契數列的生成函數，解特征方程就完了

P4191 [CTSC2010] 性能優化

循環卷積，有結論，多項式 $A(x)\times B(x)$ 的循環卷積就是 $A,B$ 分別做定長為 $n$ 的 $DFT$ 點乘起來再 $IDFT$，證明考慮單位根反演

\[\begin{aligned} &[x^k]A(x)B(x)\equiv\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}a_ib_j[(i+j) \equiv k\bmod n] \bmod (x^n-1)\\ & \equiv \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}a_ib_j\frac{1}{n}\sum_{l=0}^{n-1}\omega_{n}^{l(i+j-k)}\bmod (x^n-1)\\ & \equiv\frac{1}{n}\sum_{l=0}^{n-1}\omega_{n}^{-lk}\left( \sum_{i=0}^{n-1}a_i\omega_{n}^{li}\right)\left(\sum_{j=0}^{n-1}b_j\omega_{n}^{lj}\right)\bmod (x^n-1)\\ \end{aligned} \]

得證。

現在考慮如何計算定長為 $n$ 的 $DFT$，即 $\forall i\in[0,n-1]$，算出 $f(\omega_{n}^{i})$ 的點值，普通的 $DFT$，我們將其奇偶分組，這題中有 $n$ 的質因子小于 $10$ 的性質，對于每一個質因子 $p$，我們按 $p$ 分組

\[\begin{align} & F_k(x)=\sum_{i=0}^{\left\lfloor (n-k)/p \right\rfloor} a_{ip+k}x^{ip+k}\\ & F(\omega_{n}^{i})=\sum_{k=0}^{p-1}\omega_{n}^{kp}F_{k}(\omega_{\frac{n}{p}}^{i})\\ \end{align} \]

遞歸求解即可

7.27

模擬賽

T1

唐

T2

考慮上升序列和下降序列的交

T3

~~不會。~~

在原排列中大小相差 $1$ 的元素 $x,x+1$，若其位置分別為 $pos_x,pos_{x+1}$，則合法排列的充要條件是 $pos_x$ 和 $pos_{x+1}$ 的大小關系保持不變

這樣 $op=1$ 直接記 $f_{i,j}$ 表示大小為 $i$ 的數，在排列中的相對位置為 $j$

最小的操作次數顯然是逆序對，考慮貢獻，直接枚舉所有的逆序對進行計數，首先枚舉第一個逆序對中的數的位置，記 $f_{i,j,k}$ 為考慮了前 $i$ 個元素，第一個元素的相對位置為 $j$，第 $i$ 個元素相對位置是 $k$，直接轉移即可，可以前綴和隨便優化到 $\mathcal{O}(n^4)$

#6538. 烷基計數加強版加強版

記其生成函數為 $F(x)$，直接施 Burnside，考慮把根拼上三個兒子，考慮所有大小為 $3$ 的置換

$(1,2,3)$，三個置換環，不管怎么樣都會有不動點，則貢獻為 $F^3(x)+1$
$(1,3,2),(2,1,3),(3,2,1)$，兩個置換環，其中一個大小為 $2$，其中兩個兒子同構的時候才有不動點，則不動點的貢獻為 $3F(x^2)F(x)+1$（注意這里同構的生成函數是 $F(x^2)$ 而不是 $F(x)$ 或者 $F^2(x)$）
$(2,3,1),(3,1,2)$，一個大小為 $3$ 的置換環，三個兒子均同構的時候才有不動點，則不動點的貢獻為 $2F(x^3)+1$

最后再除以置換的個數并把根加進去，這樣就有

\[ F(x)=\frac{x(F^3(x)+3F(x^2)F(x)+2F(x^3))}{6}+1 \]

考慮牛迭， $G(x,F(x))=F(x)-\frac{x(F^3(x)+3F(x^2)F(x)+2F(x^3))}{6}-1$，若已知 $F_0(x)\equiv F(x)\bmod x^{\frac{n}{2}}$，則有

\[\begin{aligned} & F(x)=F_0(x)-\frac{G(F_0(x))}{\frac{\partial G}{\partial F_0(x)}(F_0(x))}\\ & F(x)=F_0(x)-\frac{F_0(x)-\frac{x(F_0^3(x)+3F_0(x^2)F_0(x)+2F_0(x^3))}{6}-1}{1-\frac{x}{2}F_0^2(x)-\frac{x}{2}F_0(x^2)} \\ & F(x)=\frac{F_0(x)-\frac{x}{2}F_0^3(x)-\frac{x}{2}F_0(x^2)F_0(x)-F_0(x)+\frac{x(F_0^3(x)+F_0(x^2)F_0(x)+2F_0(x^3))}{6}+1}{1-\frac{x}{2}F_0^2(x)-\frac{x}{2}F_0(x^2)} \\ & F(x)=\frac{1-\frac{x}{3}F^3(x)+\frac{x}{3}F(x^3)}{1-\frac{x}{2}F_0^2(x)-\frac{x}{2}F_0(x^2)} \\ \end{aligned} \]

注意當我們對 $G(x,F(x))$ 求關于 $F_0(x)$ 的偏導時，把 $x,F(x^2),F(x^3)$ 都當成了常數

直接牛頓迭代即可，復雜度 $\mathcal{O}(n\log n)$

P6597 烯烴計數

我們已經會數烷基了，烯烴的話，只需要考慮中間的那個碳碳雙鍵，把兩邊的合起來就行了，記 $G(x)$ 為根度數小于等于二，其他點度數小于等于三的無標號樹的生成函數，記 $H(x)$ 為烯烴的生成函數，Burnside，那么有

\[G(x)=x\frac{F(x^2)+F^2(x)}{2} \]

\[H(x)=\frac{G(x^2)+G^2(x)}{2} \]

P6598 烷烴計數

最困難的一個

我們考慮重心，這樣就變成了有根樹計數，首先拋出結論：記 $p$ 為這棵樹點等價類的個數，$q$ 為這棵樹邊等價類的個數，$s=1$ 當且僅當這棵樹的重心數量為 $2$ 且這兩個重心等價，則有 $p-q+s=1$，給出證明：

如果只有一個重心，重心不與任何點等價，這時候以重心為根，把所有邊向根定向，那么每個點連向父親的邊和那個點的等價情況一樣，則有 $p-q=1$
如果有兩個重心且這兩個重心不等價，這時有兩個重心和兩個重心的一條邊嗎，那么和上面那個情況就一樣了，有 $p-q=1$
同上，有 $p-q=0$

那么我們只需要數 $p,q,s$ 就行了

$p$ 的生成函數 $P$，直接考慮在那個點處枚舉四個烷基，用 Burside 引理，則有

\[ P(x)=x\frac{F^4(x)+6F(x^2)F^2(x)+3F(x^2)^2+8F(x^3)F(x)+6F(x^4)}{24} \]

$q$ 的生成函數 $Q$，就是考慮把兩個烷基接起來后不同構， Burnside，有

\[ Q(x)=\frac{(F(x)-1)^2+F(x^2)-1}{2} \]

這里有 $-1$ 是因為不能是單個的 H 原子

$s$ 的生成函數 $S$，就是兩個同構的烷基的生成函數，有

\[ S(x)=F(x^2) \]

最終答案的生成函數就是 $P-Q+S$

P7592 數樹（2021 CoE-II E）

隨便拉反

設 $F(x,y)=\sum f_{n,m}x^ny^m$，其中 $f_{n,m}$ 表示大小為 $n$ 的樹，有 $m$ 個 $k_1$ 叉兒子，那么有

\[F=xyF^{k_1}+xF^{k_2}+x \]

等號右邊全都有 $x$，那么考慮對 $x$ 這一維做反演，有

\[\frac{F}{yF^{k_1}+F^{k_2}+1}=x \]

那么 $F$ 的復合逆 $G$ 就是

\[G(x)=\frac{x}{yx^{k_1}+x^{k_2}+1} \]

直接拉反，就有

\[[x^n]F=\frac{1}{n}[x^{n-1}]\left(\frac{x}{\frac{x}{yx^{k_1}+x^{k_2}+1}}\right)^n=\frac{1}{n}[x^{n-1}]\left(yx^{k_1}+x^{k_2}+1\right)^n \]

現在只需要對于所有的 $m\in[0,n]$ 求 $[x^{n-1}y^m](yx^{k_1}+x^{k_2}+1)^n$，右邊那個式子怎么算？考慮枚舉每一項選了多少個，不妨設選了 $u$ 個 $yx^{k_1}$，$v$ 個 $x^{k_2}$，$w$ 個 $1$，那么有

\[\left\{\begin{matrix} u+v+w=n \\ k_1u+k_2v =n-1\\ u=m \end{matrix}\right. \]

容易發現對于一個 $m$ 最多只有一組 $u,v,w$ 是合法的，其貢獻就是 $\binom{n}{u,v,w}$，這樣就能 $\mathcal{O}(n)$ 計算了

[51Nod1676無向圖同構]

記 $f_{i,j}$ 表示從 $i$ 開始走 $j$ 步的路徑條數，我們對于所有的 $j\in[1,n]$ 求出所有的 $f_{i,j}$，把這 $n$ 個點的 $f$ 值排序后按位比較就行了

刷新頁面返回頂部

oaigoaigilowoaigiy