小孩召开法
主要发布于 洛谷博客。
我也不知道哪里可以交这个题。
感谢
PS：我也不知道这比赛叫啥。
本题解由 d2019dy，Tamaki_Iroha 和 disangan233 花费数天时间在省略了亿点细节的原题解上补充而成。
感谢 AChen，EIegia 提供的帮助。
这题是我目前做过的最毒瘤的式子题，希望不会有下一道。
题意
求长为 \(n\) 的，最长交替子序列的长度为 \(k\) 的排列个数。 \(n \leq 10^{18} ,k \leq \min(10^6 , n)\)。
做法
令 \(a_k(n)\) 为答案，有
\[a_k(n)=\sum_{j=0}^n \binom nj \sum_{2r+s=k-1} (a_{2r}(j)+a_{2r+1}(j))a_s(n-j)
\]
令 \(F_k(x)\) 为 \(a_k(x)\) 的 EGF，式子可以化为
\[F_k‘(x)=\sum_{2r+s=k-1}(F_{2r}(x)+F_{2r+1}(x))F_s(x)
\]
令 \(A(x,t)=\sum_{n,k\geq 0} a_k(n)\frac {x^n}{n!}t^k\)，\(A_1(x,t)=\sum_{k\geq 0}F_{2k}(x)t^{2k}\)，\(A_2(x,t)=\sum_{k\geq 0}F_{2k+1}(x)t^{2k+1}\)，有
\[A_1(x,t)=\frac 12(A(x,t)+A(x,-t)) \qquad A_2(x,t)=\frac 12(A(x,t)-A(x,-t))
\]
由
\[\frac {\partial A(x,t)}{\partial x}=\frac {t+1}4(A^2(x,t)+A^2(x,-t)) \qquad \frac {\partial A(x,-t)}{\partial x}=\frac {t+1}4A(x,t)A(x,-t)
\]
可得
\[\frac {\partial A_1}{\partial x} = tA_1A_2+A_1^2 \qquad \frac {\partial A_2}{\partial x}=tA_1^2+A_1A_2
\]
那么有
\[\frac {\partial(A_1^2-A_2^2)}{\partial x}=0
\]
所以可得
\[A_1^2(x,t)-A_2^2(x,t)=1
\]
令 \(b_k(x)=\sum_{j\leq k}a_k(x)\)，\(B_k\) 为其 EGF，解一下可得
\[A(x,t)=(1-t)B(x,t) \qquad B(x,t)= \frac {\frac 2\rho}{1-\frac {1-\rho}te^{\rho x}} - \frac 1{\sqrt{1-t^2}}
\]
其中 \(\rho=\sqrt{1-t^2}\)。证明如下：
考虑一个结论
\[b_k(n)=\frac 1{2^k-1}\sum_{r+2s\leq k,r\equiv k \pmod 2} (-2)^s \binom {k-s}{\frac {k+r}2}\binom ns r^n
\]
证明如下
证明的其他部分都是一些基础技巧，主要难点是倒数第二步的
\[\left(\frac {2-2\rho}{t^2}\right)^n=\sum_i\binom {n+2i}i\left(\frac {t^2}4\right)^i
\]
可以发现原式可以化成
\[\frac 1{\sqrt{1-4x}}\left(\frac {1-\sqrt{1-4x}}{2x}\right)^m = \sum_{i=0}^\infty \binom {n+2i}i x^i
\]
具体可以参考《具体数学》公式 5.72，来自 1838 年一个广义二项式级数的 paper。
这里是来自 EI 的证明：
枚举 \(r\)，接下来的问题就是快速算
\[g_k (x) = \sum_s(-2)^s \binom ns \binom {k-s}x
\]
可以证明
\[g_k(x)=-\frac 1x((2n-x)g_k(x-1)+(k-x+2)g_k(x-2)
\]
\(n=k\) 时显然，由 \(g_k (x) = g_{k?1}(x ? 1) + g_{k?1}(x)\)归纳即可。
\(O(k)\) 递推 \(g_k\)，计算快速幂即可，时间复杂度 \(O(k \log n)\) 或 \(O(k)\)。
SDOI2019 集训 小孩召开法 题解
原文：https://www.cnblogs.com/disangan233/p/12885168.html
