由于心情不好，做了一晚上的 dirty works……
首先是神仙映射。
打个暴力会发现 |sn|=n!，这意味着一个好序列很可能存在着某种精妙的与排列的映射。
结论：对于 n 阶排列 a，存在好序列 p，满足： pai=1+i−1∑j=1[aj<aj+1]
p 为好序列是显然的。
通过察看 pn…p1 可以确定 n…1 在原排列 a 中的的位置，显然这也是唯一对应的。
考虑欧拉数 ⟨nk⟩ 表示长度为 n 的排列，含有 k 个「升高」的排列个数。
令 Sk=∑p∈snfp(k+1)
则枚举 k+1 在原排列中产生的位置，显然 Sk=n∑i=max(1,k)⟨ik⟩(ni)(n−i)!
考虑求出长度为 n 的序列中钦定 k 个「升高」的方案数，二项式反演即可得到 ⟨nk⟩。
那么考虑到钦定 k 个「升高」会出现 n−k 个钦定的「升高」段，升高段内的 EGF 是显然的，因此 ⟨nk⟩=n!n∑i=max(1,k)(−1)i−k(ik)[xn](ex−1)n−i
继续一波代入 Sk=n∑i=max(1,k)⟨ik⟩(ni)(n−i)!=n∑i=max(1,k)(ni)(n−i)!i!i∑j=k(−1)j−k(jk)[xi](ex−1)i−j=n!k!n∑j=k(−1)j−kj!(j−k)!n∑i=max(1,j)[xi](ex−1)i−j
看出了卷积形式，令 Wk=n∑i=k[xi](ex−1)i−k
处理一下需要提取系数的项 Wk=n∑i=k[xi](ex−1)i−k=[xk]n∑i=k(ex−1x)i−k=[xk]n−k∑i=0(ex−1x)i
令 F(x)=ex−1x，则 Wk=[xk]1−Fn−k+1(x)1−F(x)=[xk]11−F(x)−[xk]Fn−k+1(x)1−F(x)
前一项考虑如此处理求逆 [xk]11−F(x)=[xk+1]x1−F(x)
后一项先推导亿下 [xk]Fn−k+1(x)1−F(x)=[xn+1](xF(x))n−k+11−F(x)
鏼爷的论文启发我们使用二元生成函数 [xn+1](xF(x))n−k+11−F(x)=[xn+1wn−k+1]1(1−F(x))(1−wxF(x))
那么到此我们将求 Wk 转为求以上生成函数的 xn+1 项系数。
尝试探求扩展拉格朗日反演的科技，考虑构造某两个函数的复合 H(G(x)) 恰为以上生成函数，且 G(x) 的复合逆容易求得。
令 G(x)=xF(x)=ex−1，为了构造 H 同时需要构造 P(G(x))=F(x)。
显然 P(G(x))=F(x)⟺P(xF(x))=F(x)⟺P(x)=xG−1(x)=xln(1+x)
注意指数上的 −1 表示函数幂。
从而有 H(x)=1(1−P(x))(1−wx)
根据扩展拉格朗日反演有 [xn+1]H(G(x))=1n+1[xn]H′(x)(xG−1(x))n+1=1n+1[xn]H′(x)Pn+1(x)
好的那么先来一波喜闻乐见的 dirty works：关于 x 对 H(x) 求导： H′(x)=(1(1−P(x))(1−wx))′=(11−P(x))′11−wx+11−P(x)(11−wx)′=P′(x)(1−P(x))2(1−wx)+w(1−P(x))(1−wx)2
不用再推下去了，因为接下来只需要这样的形式，刚刚好。
还在本蒟蒻可接受范围之内（
好的那么接下来又是一波 dirty works：xjb 代入 [xn+1]H(G(x))=1n+1[xn]H′(x)Pn+1(x)=1n+1[xn](P′(x)(1−P(x))2(1−wx)+w(1−P(x))(1−wx)2)Pn+1(x)=1n+1[xn](P′(x)(1−P(x))2∑i≥0wixi+11−P(x)∑i≥0(i+1)wi+1xi)Pn+1(x)
提取你的系数，令 i=n−k+1： [wixn]H′(x)Pn+1(x)=[wixn](P′(x)(1−P(x))2∑i≥0wixi+11−P(x)∑i≥0(i+1)wi+1xi)Pn+1(x)=[xn](P′(x)xi(1−P(x))2+ixi−11−P(x))Pn+1(x)=[xn−i+2]x2P′(x)Pn+1(x)(1−P(x))2+[xn−i+2]ixPn+1(x)1−P(x)=[xk+1]x2P′(x)Pn+1(x)(1−P(x))2+[xk+1](n−k+1)xPn+1(x)1−P(x)
这东西推出式子之后实现也是很容易出锅的……建议好好整理一下流程再写。
代码：
1 |
|