數學專題 1

1. 夢現時刻

   生成函數簡單題。

   發現這個異或沒有性質，所以一定是求出所有的 \(F(a, b)\)。

   考慮如何做，我們寫出其一行的生成函數：

   \[\begin{aligned} \cal F_b &= \sum_a x^a \sum_i^b \dbinom bi \dbinom {n - i}a \\ &= \sum_i^b \dbinom bi \sum_a \dbinom {n - i}a x^a \\ &= \sum_i^b \dbinom bi (1 + x)^{n - i} \\ &= (1 + x) ^ n\sum_i^b \dbinom bi (1 + x)^{-i} \\ &= (1 + x) ^ n (1 + (1 + x)^{-1})^b \\ &= (1 + x) ^ {n - b} (2 + x)^b \\ \end{aligned}\]

   考慮如何提取其一行的系數，考慮遞推，設 \(f_i = [x^i]\cal F_b\) 我們發現：

   \[(1 + x)(2 + x)\frac{\rm d}{\rm dx} \cal F_b = F_b(2n - b + nx) \]

   于是有：

   \[2(i + 1)f_{i + 1} + 3if_t + (t - 1)f_{t - 1} = nf_{t - 1} + (2n - b)f_t \]

   然后就可以遞推了，這個方法還是通用的。

2. Swaps

   容易想到連邊，然后就是分討一下環和鏈，實現難度在基環樹找環。

3. Partial Virtual Trees

   首先轉化成講每個節點打一個刪除時間的 tag \(p_u\)，這樣可以輕松刻畫第二個限制，即 \(\sum_{v \in son_u}[p_v > p_u] \le 1\)。

   對于第一個限制，我們容斥一下即可。

   這是非常好 dp 的，枚舉 \(v \text{ s.t. } p_v > p_u\) 即可，前綴優化即可 \(\cal O(n ^ 2)\)。

   注意到 dp 值不一定有逆元，所以有一步要寫成前后綴積。

4. 冒泡排序

   type 1 很簡單的。

   type2 考慮到每次相當于是前綴最大值不會操作，其余會操作。這啟發我們建笛卡爾樹。

   先欽定最大值在最后，一會再考慮位移。這樣不能操作的部分顯然是根的左鏈長度。

   考慮位移，首先位移過去的點顯然是必然操作，然后相當于是將其右兒子替換它，這樣原本的根的左鏈長度就變成了走向一個節點的最長左走步數。

   然后就是簡單 dp 了。

5. Basis

   首先你得會一個正常人類都會的莫反：

   \[f(n) = \sum_{d | n} g(d) \iff g(n) = \sum_{d | n} \mu(\frac nd) f(d) \]
   \[f(n) = \sum_{n | d} g(d) \iff g(n) = \sum_{n | d} \mu(\frac dn) f(d) \]

   考慮只有 \(G\) 怎么做，發現其相當于是顏色無關，只和下標有關，可以看成 \(n\) 個球放到 \(m\) 個盒子中，盒子不區分，就是第二類斯特林數。

   當然也可以先寫個 \(dp\) 然后一眼看穿，于是我們可以 \(n\log n\) 求一行。

   考慮加上 \(F\)，則多一個每個連續段的 \(\gcd = 1\)，考慮莫反，設 \(f(x)\) 表示連續段 \(\gcd\) 為 \(x\) 的倍數的方案數，然后就做完了。

6. Stairs

   簡單題。

   首先顯然可以還原出每個連續段。

   然后直接容斥，問題變成將原有的連續段劃分成 \(k\) 個連續段的方案，直接 dp 上前綴和優化是 \(n ^ 2\) 的。

   我們發現 dp 的轉移十分簡單，于是直接將轉移的生成函數寫成矩陣，跑分治 NTT 即可。

7. Test Data Generation

   倍增 FFT 板子，思考沒難度。

   枚舉一個 \(2 ^ k\)，將所有數除掉 \(2 ^ k\) 使 \(a_n\) 是奇數即可。

8. Jellyfish and OEIS

   學習 特化析合樹

   然后寫個區間 dp 限制一下限制就做完了。

9. Construct a Matrix

   簡單題。

   首先將 \(0\) 去掉，然后發現 \(\times 1\) 不變，\(\times 2\) 相當于是改變奇偶性，相當于是異或。

   寫個高消，二維前綴和優化即可。

10. Stranger Trees

    直接容斥，連通塊間的方案數是很簡單的，于是問題就是劃分聯通塊。

    直接 dp 即可 \(n ^ 3\)，但是我們發現連通塊大小 \(a\) 的系數是 \(\prod a\)，這樣可以用一個 trick 就是將系數看成在每個連通塊中選一個點，記錄是否選擇即可 \(n^2\)。

    當然用 matrix-tree 加站位元可以直接做到 \(n ^ 4\)。

剩下兩個是 LGV 題，直接看 鮮花 即可。