EX 1.1 习题

\[ \rm{Define\ \LaTeX \ Macros\ Here} \newcommand\stirA[2]{\begin{bmatrix}#1\\ #2\end{bmatrix}} \newcommand\stirB[2]{\begin{Bmatrix}#1\\ #2\end{Bmatrix}} \newcommand\ul[1]{\underline{#1}} \newcommand\dis{\operatorname{dis}} \newcommand\edp{\operatorname{edp}} \newcommand\Endpos{\operatorname{Endpos}} \newcommand\Startpos{\operatorname{Startpos}} \newcommand\height{\operatorname{height}} \newcommand\SA{\operatorname{SA}} \newcommand\len{\operatorname{len}} \newcommand\chkmax{\operatorname{chkmax}} \newcommand\chkmin{\operatorname{chkmin}} \newcommand\siz{\operatorname{siz}} \newcommand\fa{\operatorname{fa}} \newcommand\LCP{\operatorname{LCP}} \newcommand\EGF{\operatorname{EGF}} \newcommand\OGF{\operatorname{OGF}} \]

基础技术

P4931 [MtOI2018] 情侣？给我烧了！

首先考虑二项式反演，令 \(g(n,k)\) 表示 \(n\) 对恰好有 \(k\) 对坐在一起的方案数，\(h(n,k)\) 表示所有先选定 \(k\) 个，其他任意排的方案数之和。

\[ g(n,k)=\sum_{i=k}^{n}(-1)^{i-k}\binom{i}{k}h(n,i) \]

而

\[ h(n,i)=\binom{n}{i}^2i!2^i(2(n-i))! \]

先选定 \(i\) 个座位，在选定 \(i\) 对情侣，这 \(i\) 对可以左右任意换，其他 \(2(n-i)!\) 个任意排。

试图预处理 \(g(n,k)\) 只能得到一个 \(\mathcal O(n^3)\) 预处理的做法，每次重算是 \(\mathcal O(Tn^2)\) 的，都不太行。

考虑先选定 \(k\) 对坐在一起，再乘上剩下的一对都不交的方案数。

\[ \binom{n}{k}^2k!2^k\cdot g(n-k,0) \]

那么问题即求出 \(c=0,1,2,\cdots, n\) 的 \(g(c,0)\)。

\[ g(c,0)=\sum_{i=0}^{c}(-1)^{i}\binom{c}{i}^2i!2^i(2(c-i))! \]

这是可以 \(\mathcal O(n^2)\) 预处理的。

显然问题就在于处理 \(g(c, 0)\) 上，考虑优化其处理，下面 \(g(c,0)\) 简记为 \(g(c)\)。

总之先化成卷积的形式，把 \((n-i)\) 和 \(i\) 分别放一起。 $$ \begin{aligned} g(n)&=\sum_{i=0}^{n}(-1)^i\qty(\frac{n!}{(n-i)!i!})^2i!2^i(2(n-i))!\ &=(n!)^2\sum_{i=0}^{n}\frac{(2(n-i))!}{(n-i)!^2}\cdot \frac{(-2)^i}{i!} \end{aligned} $$

设 \(a(n)=\frac{(2n)!}{n!^2},b(n)=\frac{(-2)^n}{n!}\)，它们对应的 \(\OGF\) 分别为 \(A(x),B(x)\)。 $$ A(x)=\sum_{n=0}^{\infty}\frac{(2n)!}{n!^2}x^n=\sum_{n=0}^{\infty}\binom{2n}{n}x^n=\dfrac{1}{\sqrt{1-4x}} $$

\[ B(x)=\sum_{n=0}^{\infty}\frac{(-2)^n}{n!}x^n=\exp(-2x)\\ \]

考虑

\[ G(x)=\frac{\mathrm{e}^{-2x}}{\sqrt{1-4x}} \]

凑点 ODE 出来： $$ G'(x)=\frac{\mathrm{e}^{-2x}\cdot 8x}{(1-4x)^{3/2}}\ \frac{1-4x}{8x}G'(x)=G(x)\ G'(x)=4x\cdot G'(x)+8x\cdot G(x) $$ 即： $$ g(n)=\frac{4(n-1)g(n-1)+8g(n-2)}{n} $$

简单运用