又是 dirty works……(
首先有 DP fn=sn+1(n3)n∑i=1(i−1)(n−i)(fk+fn−k)
随便化一下可得 (n3)fn=(n3)sn+2n∑i=1(n−i−1)ifi
写成生成函数的形式就是 F(3)(x)=S(3)(x)+12(1−x)2F′(x)(1−x)3F(3)−12(1−x)F′=S(3)
我也不知道为什么定义算子 θF(x)=(1−x)F′(x)
(注意这里的定义和题解不一样)
然后可以发现 θ2F=(1−x)2F″−(1−x)F′θ3F=(1−x)3F(3)−3(1−x)2F″+(1−x)F′
因此 (θ3+3θ2−10θ)F=S(3)θ(θ−2)(θ+5)F=(1−x)3S(3)
令 Q=(θ+5)F,P=(θ−2)Q,则有 {θP=(1−x)3S(3)(θ−2)Q=P(θ+5)F=Q
提取系数得 {(n+1)pn+1=npn+▽3sn+3(n+3)3_(n+1)qn+1=(n+2)qn+pn(n+1)fn=(n−5)fn+qn
从第一条式子有 npn=▽2sn+2(n+2)3_
再代入第二条式子,展开得 qn+1n+2=qm+1m+2+n+1∑i=m+3▽2si
再代入第三条式子,展开得 (n6)fn=(m+16)fm+1+qm+1m+2n∑i=m+2(i6)+n∑i=m+2(i6)i∑j=m+3▽2sj
显然有 fm+1=sm+1,fm+2=sm+2
然后 pm+1=(m+2)fm+2−(m−4)fm+1
再一通乱算可以得到 fn=sn+12(n6)n−1∑i=m+1fi(i+1)(i+2)((n+17)−(i+27))
使用线段树维护即可。
代码:
1 |
|