CF1349F2
从小到大，从后往前放，即写出一个放东西的顺序序列 { p i } \{p_i\} {pi}，将其划分成若干段极长的下降序列，每一段从小到大对应一个数字。假设要求出 t t t 的答案，我们可以枚举每个处于第 t t t 个下降序列的位置并统计它的贡献 ∑ i ways i , t ( n i ) ( n − i ) ! \sum_{i}\text{ways}_{i,t}\binom{n}{i}(n-i)! ∑iwaysi,t(in)(n−i)! 其中 ways i , j \text{ways}_{i,j} waysi,j 表示长为 i i i 的排列，划分成 j j j 个极长下降段的方案数 这显然是可以容斥的 ways i , j = ∑ k ≥ j { i i − k } ( i − k ) ! ( − 1 ) k − j ( k j ) \text{ways}_{i,j}=\sum_{k\ge j}\begin{Bmatrix}i\\i-k\end{Bmatrix}(i-k)!(-1)^{k-j}\binom{k}{j} waysi,j=k≥j∑{ii−k}(i−k)!(−1)k−j(jk) 即对每一个 t t t 算出 n ! ∑ i ≤ n ∑ k [ z i ] ( e z − 1 ) i − k ( − 1 ) t − k ( t k ) = n ! ∑ k ( − 1 ) t − k ( t k ) ∑ i ≤ n [ z i ] ( e z − 1 ) i − k n!\sum_{i\le n}\sum_{k}[z^i](e^z-1)^{i-k}(-1)^{t-k}\binom{t}{k}\\=n!\sum_{k}(-1)^{t-k}\binom{t}{k}\sum_{i\le n}[z^i](e^z-1)^{i-k} n!i≤n∑k∑[zi](ez−1)i−k(−1)t−k(kt)=n!k∑(−1)t−k(kt)i≤n∑[zi](ez−1)i−k 对每个 k k k 求出 ∑ k ≤ i ≤ n [ z i ] ( e z − 1 ) i − k = ∑ k ≤ i ≤ n [ z k ] ( e z − 1 z ) i − k \sum_{k\le i\le n}[z^i](e^z-1)^{i-k}\\=\sum_{k\le i\le n}[z^k](\frac{e^z-1}{z})^{i-k} k≤i≤n∑[zi](ez−1)i−k=k≤i≤n∑[zk](zez−1)i−k 设 f = e z − 1 z , g = e z − 1 f=\frac{e^z-1}{z},g=e^z-1 f=zez−1,g=ez−1 即求 [ z k ] f n − k + 1 − 1 f − 1 = [ z n + 1 ] g n − k + 1 − 1 f − 1 [z^k]\frac{f^{n-k+1}-1}{f-1}=[z^{n+1}]\frac{g^{n-k+1}-1}{f-1} [zk]f−1fn−k+1−1=[zn+1]f−1gn−k+1−1 一个技巧是，若要对每个 k k k 求出 [ z n ] F ( z ) G ( z ) k [z^n]F(z)G(z)^k [zn]F(z)G(z)k 我们写成 [ z n u k ] ∑ i F ( z ) ( u G ( z ) ) i = F ( z ) 1 − u G ( z ) [z^nu^k]\sum_{i}F(z)(uG(z))^i=\frac{F(z)}{1-uG(z)} [znuk]i∑F(z)(uG(z))i=1−uG(z)F(z) 然后进行拉格朗日反演
[ z n u k ] F ( z ) 1 − u G ( z ) = [ z n − 1 u k ] 1 n ( F ( G − 1 ( z ) ) 1 − u z ) ′ ( z G ( z ) ) n = [ z n − 1 u k ] 1 n ( u F ( G − 1 ( z ) ) ( 1 − u z ) 2 + F ( G − 1 ( z ) ) ′ 1 − u z ) ( z G ( z ) ) n [z^nu^k]\frac{F(z)}{1-uG(z)}=[z^{n-1}u^k]\frac{1}{n}(\frac{F(G^{-1}(z))}{1-uz})'(\frac{z}{G(z)})^n\\=[z^{n-1}u^k]\frac{1}{n}(\frac{uF(G^{-1}(z))}{(1-uz)^2}+\frac{F(G^{-1}(z))'}{1-uz})(\frac{z}{G(z)})^n [znuk]1−uG(z)F(z)=[zn−1uk]n1(1−uzF(G−1(z)))′(G(z)z)n=[zn−1uk]n1((1−uz)2uF(G−1(z))+1−uzF(G−1(z))′)(G(z)z)n 套用到这道题上就可以了
