令 ak(n) 为答案。
为了导出递推式,我们考虑一下原问题。
注意到必然至少存在一个最长交替子序列经过最大值 n,于是考虑枚举 n 的位置为 i。
然后首先要从 n−1 个数中选择 i−1 个放到左边。
接下来考虑两边分配的交替子序列长度。枚举 2r+1+s=k,那么左边可以有 2r 或 2r+1 的交替子序列(因为 n 可以替换掉 2r+1 处的),右边可以有 s 的交替子序列。
因此 fk(n)=n∑i=1(n−1i−1)∑2r+s=k−1(f2r(i−1)+f2r+1(i−1))fs(n−i)
设 BGF F(x,t)=∑fk(n)xnn!tk,F0(x,t)=∑f2k(n)xnn!t2k,F1(x,t)=∑f2k+1(n)xnn!t2k+1。
那么根据如上递推式,我们有 ∂F∂x=(tF0+F1)F∂F0∂x=(tF0+F1)F1∂F1∂x=(tF0+F1)F2
然后注意到 ∂(F20−F21)∂x=∂F20∂x−∂F21∂x=0
这样对于 F20−F21,我们只需要对照常数。而根据定义仅有 F0 在 x0 处有 1,因此 F20−F21=1=(12(F(x,t)+F(x,−t)))2−(12(F(x,t)−F(x,−t))2=F(x,t)F(x,−t)
则 ∂F∂x=(tF0+F1)F=12((t+1)F+(t−1)F−1)F∂F((t+1)F+(t−1)F−1)F=∂x2
设 G=F1−t,则 F=(1−t)G。代入得 ∂G(1−t2)G2−1=∂x2
令 α=√1−t2,我们作部分分式分解,就有 ∂(αG)(1αG−1−1αG+1)=α∂xlnαG−1αG+1=αx+C′αG−1αG+1=eαx+C′=eαxCG=1+Ceαxα(1−Ceαx)
其中 C′,C=eC′ 关于 x 都是常数。
然后注意到 B(0,t)=11−t,因此 C=α1−t−1α1−t+1=1−αt
因此 G=1α(21−Ceαx−1)=1α(21−1−αteαx−1)
我们显然可以不管 [x0],接下来尝试提取其系数 2α(1−1−αteαx)−1=2α∑r(1−αteαx)r=2α∑r(1−αt)r∑s(rαx)ss!=2∑rt−r∑s(rx)ss!(1−α)rαs−1
在出题人给出的标准做法中,这里凑出了一个有趣的形式,然后利用具体数学中提到的恒等式来辅助推导,但未免太过匪夷所思,这里展示一种更暴力却也更自然的做法(虽然最后推得的结果形式也不尽相同)。
我们想要展开 (1−√1−t2)r(1−t2)(s−1)/2
不妨作换元,令 4x=t2,则 t24=x,且原式变为 (1−√1−4x)r(1−4x)(s−1)/2
令 F 满足二叉树方程 F=x(1+F)2 就有熟知结论 F=1−2x−√1−4x2x,x=F(1+F)2
我们把原式整理成复合形式 (1−√1−4x)r(1−4x)(s−1)/2=(2x(1+F))r(1−2x−2xF)s−1=2rxr(1+F)r(1−2x(1+F))s−1=2rFr(1−F)s−1(1+F)−r−s+1
然后使用另类拉格朗日反演提取系数 [xn]Fr(1−F)r−1(1+F)−r−s+1=[xn]xr(1−x)r−1(1+x)−r−s+11−x(1+x)3(1+x)2n+2=[xn]xr(1−x)r(1+x)2n−r−s=∑i(−1)i(ri)(2n−r−sn−r−i)
代回到原式,就有 =2∑rt−r∑s(rx)ss!2r∑l(t24)l∑i(−1)i(si)(2l−r−sl−r−i)=2∑rt−r∑s(rx)ss!2r∑u(t24)r+u∑i(−1)i(si)(r+2u−su−i)=∑r,s,u21−r−2utr+2u(rx)ss!∑i(−1)i(si)(r+2u−su−i)
则令 n=s,k=r+2u,便知 gk(n)=21−k∑2i+r≤k,r≡k(mod2)rn(−1)i(ni)(k−nk−r2−i)
枚举 r,则需要计算形如 ft=∑i(−1)i(ni)(−st−i)
的数列。
考虑其生成函数,显然其为 F(x)=(1+x)−s(1−x)n
求导 F′=−sF1+x−nF1−x
即 tft=−(n+s)ft−1+(s−n+t−2)ft−2
时间复杂度 O(klogkn)。
感觉这题有意思的地方主要在于最前面的 DP 和微分方程部分,以及后面的提取系数部分。
由于这个题很明显是先想题意再想做法的,所以想复刻这种做法的题目还是比较无从下手(好像暴露了啥
代码:
1 |
|