鱼写的那条引理大致是对的，但不知道是不是笔误，$\Sigma$ 的下指标应该写成 $0$。这关乎在考虑一个和式时，如果上指标小于下指标，应该如何定义它。

这里主要考虑 $n=0$ 时，如果那个和式，预先使得 $g(0)$ 为某个值，那么这个定义在本题是失败的，因为希望只保留 $g$ 之间的递推关系而不给 $g$ 赋初值。

至于为什么希望只保留递推关系可以参考 loj6054。

所以最好让 $n$ 取 $0$ 这个边界时，有两边 $0=0$。如果你认为 $n=0,1$ 都取 $0$ 那也说不通吧。$\Sigma$ 的下指标应该写成 $0$。

当然你也可以让这个下指标更小一点，只要它包含 $0$ 就好，因为鱼后边的优化用到了 $g(0)$ 是有定义的这个前提。

还要注意 $a$ 的几个没有意义的取值。$a=0$ 显然没意义；$a=1$ 这个和式就是一个经典的多项式前缀和问题，它本身就是一个次数为 $\deg f+1$ 的多项式。

---

纵上俺擅自对鱼写的引理做了一点小改动。

$\texttt{Theorem}$

已知常数 $a\not= 0,1$，有 $f,g$ 满足

$$a^ng(n)-a^0g(0)=\sum\limits_{i=0}^{n-1}a^if(i)$$

若 $f$ 是一个 $k$ 次多项式，那么 $g$ 存在唯一的多项式解，其次数为 $k$。

相信大家都会证。 这个解等价于递推式

$$g(n+1)=\frac{1}{a}g(n)+\frac{1}{a}f(n)$$

（可能还要加上 $n\ge 0$ 这个条件）的解。$\frac{1}{a}f(n)$ 是个 $k$ 次多项式，$\frac{1}{a}\not=1$。

考虑 $g$ 的多项式解。若 $\deg g\not= \deg f$，直接考虑两边的最高次项的系数，发现它们不可能相同，所以不存在；反之 $\deg g= \deg f$，对比 $g(n+1)-\frac{1}{a}g(n)$ 和 $\frac{1}{a}f(n)$ 的系数，用矩阵写出它们的关系，发现是一个上（下）三角矩阵，行列式非零，这样就构造出了 $g$ 的 $k$ 次多项式解，并说明了唯一性。

$\square$

这题和 loj6054 其实是同一个思路，将一个前缀和写回递推式，化成

$$g(x+1)=\lambda g(x)+f(x)$$

其中 $\lambda\not=1$，$f(x)$ 为已知多项式。根据 $g$ 存在唯一多项式解这个结论然后优化一下就好了。

这个引理在俺看来应该是根据鱼题解后面给出的那个递推式才推得的。

因此俺把这个贴在讨论区防止后人直接去刚那条引理。如果真的能直接刚出来欢迎 D 我。

如果你觉得俺说那个矩阵是上三角矩阵纯口嗨，需要更形式化一点，可以私戳俺。