题解

· · 个人记录

T2：幂

算法1：

设\{a_n\}是等差数列，首项为a_1，公差为d。

设\{b_n\}是等比数列，首项为b_1，公比为q(\,\left|\,q\,\right|\lt1) 。

设S(x)=\sum_{i=1}^{\infty}a_ib_i，则

S(x)=a_1b_1+(a_1+d)b_1q+(a_1+2d)b_1q^2+\cdots \ \ \ \ \ \ \ \,\,=b_1\big[a_1(1+q+q^2+\cdots)+dq(1+2q+3q^2+\cdots)\big] \ \ \ \ \ \ \ \,\,=b_1\big[a_1\frac{1}{1-q}+dq(\frac{1}{1-q})^2\big] \ \ \ \ \ \ \ \,\,=\frac{b_1}{1-q}\big(a_1+d\cdot \frac{q}{1-q}\big)

若\{a_n\}为m阶等差数列。

设d_0,d_1,d_2,\dots d_m为数列\{a_n\}的0,1,2,\dots m阶差数列的首项。

则S(x)=\sum\limits_{i=1}^{\infty}a_ib_i=\frac{b_1}{1-q}\sum\limits_{i=0}^m d_i(\frac{q}{1-q})^i

证明：m=1时，显然d_0=a_1，d_1=d，原式成立。

现在假设m=r时成立，下面证明m=r+1时也成立。

设\{\Delta_n\}=\{a_{n+1}-a_n\}，那么\{\Delta_n\}是r阶等差数列

则\sum\limits_{i=1}^{\infty}\Delta_ib_i=\frac{b_1}{1-q}\sum\limits_{k=0}^r d_{k+1}(\frac{q}{1-q})^k

设\sum\limits_{i=1}^{\infty}\Delta_ib_i的前n项和为D_n，\sum\limits_{i=1}^{\infty}a_ib_i的前n项和为S_n。

则\lim\limits_{n\to \infty}D_n=\frac{b_1}{1-q}\sum\limits_{k=0}^r d_{k+1}(\frac{q}{1-q})^k

考虑S_n=a_1b_1+a_2b_2+a_3b_3+\cdots+a_nb_n

qS_n=a_1b_2+a_2b_3+a_3b_4+\cdots+a_nb_{n+1} \big(1-q\big)S_n=a_1b_1-a_nb_{n+1}+(a_2-a_1)b_2+(a_3-a_2)b_3+\cdots+(a_n-a_{n-1})b_n \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \,\,=a_1b_1-a_nb_{n+1}+\Delta_1b_2+\Delta_2b_3+\cdots+\Delta_{n-1}b_n \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \,\,=a_1b_1-a_nb_{n+1}+q\big(\Delta_1b_1+\Delta_2b_2+\cdots+\Delta_{n-1}b_{n-1}\big) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \,\,=a_1b_1-a_nb_{n+1}+qD_{n-1} S(x)=\lim\limits_{n\to \infty}S_n=\frac{1}{1-q}\big(a_1b_1-\lim_{n\to \infty}a_nb_{n+1}+q\lim_{n\to \infty}D_{n-1}\big)

分开考虑，由于\{a_n\}是r+1阶的等差数列，那么必然可以表达成r+1次多项式。

那么\lim\limits_{n\to \infty}a_nb_{n+1}=\lim\limits_{n\to \infty}\sum\limits_{k=0}^{r+1}c_kn^k\cdot b_1q^n=b_1\sum\limits_{k=0}^{r+1}c_k\lim\limits_{n\to \infty}n^kq^n

单独考虑每一个k，那么有

\lim\limits_{n\to \infty}\frac{|(n+1)^kq^{n+1}|}{|n^kq^n|}=\lim\limits_{n\to \infty}\big|q(1+\frac{1}{n})^k\big|=\big|q\big|\lt 1

那么\lim\limits_{n\to \infty}n^kq^n=0\ \ (k=0,1,2,\dots,r+1)

则\lim\limits_{n\to \infty}a_nb_{n+1}=0

又显然\lim\limits_{n\to \infty}D_{n-1}=\lim\limits_{n\to \infty}D_{n}=\frac{b_1}{1-q}\sum\limits_{k=0}^r d_{k+1}(\frac{q}{1-q})^k，所以

S(x)=\frac{1}{1-q}\big(a_1b_1+q\frac{b_1}{1-q}\sum\limits_{k=0}^r d_{k+1}(\frac{q}{1-q})^k\big) \ \ \ \ \ \ \ \,\,=\frac{b_1}{1-q}\big(a_1+\frac{q}{1-q}\sum\limits_{k=0}^r d_{k+1}(\frac{q}{1-q})^k\big) \ \ \ \ \ \ \ \,\,=\frac{b_1}{1-q}\big(a_1+\sum\limits_{k=1}^{r+1} d_k(\frac{q}{1-q})^k\big) \ \ \ \ \ \ \ \,\,=\frac{b_1}{1-q}\sum\limits_{k=0}^{r+1} d_k(\frac{q}{1-q})^k

故m=r+1时成立。

归纳得S(x)=\frac{b_1}{1-q}\sum\limits_{k=0}^m d_k(\frac{q}{1-q})^k

下面考虑怎么计算d_k。

d_k=\sum\limits_{i=0}^k(-1)^i\binom{k}{i}a_{k+1-i}

首先d_0=a_0，符合上面式子。

假设k=r时上式成立，下面证明k=r+1时成立。

令p_r表示a_2,a_3,\dots a_{r+2}作差分时r阶差数列的首项，那么p_r=\sum\limits_{i=0}^r(-1)^i\binom{r}{i}a_{r+2-i}。

则d_{r+1}=p_r-d_r=\sum\limits_{i=0}^r(-1)^i\binom{r}{i}a_{r+2-i}-\sum\limits_{i=0}^r(-1)^i\binom{r}{i}a_{r+1-i}

=\sum\limits_{i=1}^r(-1)^i\binom{r}{i}a_{r+2-i}-\sum\limits_{i=0}^{r-1}(-1)^i\binom{r}{i}a_{r+1-i}+a_{r+2}-(-1)^ra_1 =\sum\limits_{i=1}^r(-1)^i\binom{r}{i}a_{r+2-i}+\sum\limits_{i=1}^r(-1)^i\binom{r}{i-1}a_{r+2-i}+a_{r+2}-(-1)^ra_1 =\sum\limits_{i=1}^r(-1)^i\big(\binom{r}{i}+\binom{r}{i-1}\big)a_{r+2-i}+a_{r+2}-(-1)^ra_1 =\sum\limits_{i=1}^r(-1)^i\binom{r+1}{i}a_{r+2-i}+a_{r+2}+(-1)^{r+1}a_1 =\sum\limits_{i=0}^{r+1}(-1)^i\binom{r+1}{i}a_{r+2-i}

故k=r+1时成立。

归纳得d_k=\sum\limits_{i=0}^k(-1)^i\binom{k}{i}a_{k+1-i}

将d_k的式子拆开。

d_k=\sum\limits_{i=0}^k(-1)^i\binom{k}{i}a_{k+1-i}=k!\sum\limits_{i=0}^k\frac{(-1)^i}{i!}\cdot\frac{a_{k+1-i}}{(k-i)!}

多项式多点求值+\mathrm{NTT}即可。

带入答案式子，Ans=S(x)+a_0b_0=\frac{b_1}{1-q}\sum\limits_{k=0}^m d_k(\frac{q}{1-q})^k+a_0

算法2：

令f_k=\sum\limits_{n=0}^{\infty}n^kr^n

那么 r\cdot f_k=\sum\limits_{n=0}^{\infty}n^kr^{n+1}=\sum\limits_{n=1}^{\infty}(n-1)^kr^n

(1-r)f_k=\sum\limits_{n=1}^{\infty}\big(n^k-(n-1)^k\big)r^n ~~~~~~~~~~~~~\,=r\sum\limits_{n=0}^{\infty}\big((n+1)^k-n^k\big)r^n ~~~~~~~~~~~~~\,=r\sum\limits_{n=0}^{\infty}\sum\limits_{i=0}^{k-1}\binom{k}{i}n^ir^n ~~~~~~~~~~~~~\,=r\sum\limits_{i=0}^{k-1}\binom{k}{i}\sum\limits_{n=0}^{\infty}n^ir^n ~~~~~~~~~~~~~\,=r\sum\limits_{i=0}^{k-1}\binom{k}{i}f_i

故有f_k=\frac{r}{1-r}\sum\limits_{i=0}^{k-1}\binom{k}{i}f_i

化一下式子，\frac{f_k}{k!}=\sum\limits_{i=0}^{k-1}\frac{f_i}{i!}\big(\frac{r}{1-r}\cdot \frac{1}{(k-i)!}\big)，很明显分治fft可以解决这个问题。

最后很明显Ans=\sum\limits_{i=0}^ma_if_i

T3：序列

ODT裸题

还看到dalao们有用treap过的