【省選模拟】20/06/08

A A A

• 考慮容斥，1表示欽定選，0 的位置表示 0/1 均合法，這樣的好處是可以隻考慮 1 的限制

  并且最後我們隻需對超集容斥就可以得到答案

  發現欽定一些 1 選的意義就是在原圖上選若幹條不相交的鍊，複雜度和拆分數有關

  預處理一個集合有多少條鍊，那麼就是一個子集卷積

  并且發現隻用求出最後一項，是以可以 O ( 2 n ) O(2^n) O(2n) 暴力容斥回去

  複雜度 O ( n 2 2 n + p ( n ) 2 n ) O(n^22^n+p(n)2^n) O(n22n+p(n)2n)， p ( n ) p(n) p(n) 為拆分數， C o d e Code Code

B B B

• 考慮在 S l , r S_{l,r} Sl,r​ 的前後加字元，求的就是本質不同的方案數

  在前面的方案數對應的就是子樹中字尾結點的 l e n u − l e n l i n k u len_u-len_{link_u} lenu​−lenlinku​​

  下面要求出在後面加字元的方案數，用字尾數組求出本質不同的個數，啟發式合并

  C o d e Code Code

C C C

• 顯然轉移可以寫成如下形式

  f i i = ∑ j = 1 i f j − 1 f i − j x min ⁡ ( j , i − j + 1 ) \frac{f_i}{i}=\sum_{j=1}^if_{j-1}f_{i-j}x^{\min(j,i-j+1)} ifi​​=j=1∑i​fj−1​fi−j​xmin(j,i−j+1)

  發現項數是 750 左右，可以将其視為 O ( n ) O(n) O(n)，複雜度 O ( n 3 ) O(n^3) O(n3)

  C o d e Code Code