设 P′i 表示一次操作后的 P(x=i)。
再设 F,F′ 分别为 P,P′ 的生成函数。
注意到 P′i=n∑j=iPjj+1。
故 F′(x)=n∑i=0P′ixi=n∑i=0xin∑j=iPjj+1=n∑j=0Pjj+1j∑i=0xj=n∑j=0Pjj+1⋅xj+1−1x−1=1x−1n∑j=0Pjxj+1−Pjj+1=1x−1∫x1(n∑j=0Pjtj)dt=1x−1∫x1F(t)dt
然而这要怎么算啊……
考虑设 G(x)=F(x+1),G′(x)=F′(x+1)。
于是 G′(x)=F′(x+1)=1x∫x0G(t)dt
若 gi=[xi]G(x),g′i=[xi]G′(x),则 g′i=gii+1。
做 m 次的话就是 gi(i+1)m。
但是如何在 P,g 间转化呢?
首先考虑从 P 求 g。
有 G(x)=F(x+1)=n∑i=0Pi(x+1)i=n∑i=0Pii∑j=0(ij)xj=n∑j=0xjn∑i=jPi(ij)
即 gi=n∑j=iPj(ji)。
再推一推 gi=n∑j=iPj(ji)=n∑j=ij!Pji!(j−i)!i!gi=n∑j=ij!Pj(j−i)!=n−i∑j=0(i+j)!Pi+jj!
翻转一下就是卷积了。
从 g′ 转回 P′ 类似。
代码:
1 |
|