Операция суммирования и удобный базис для неё

[MetaMorphy]

Всем привет.

Рассмотрим множество многочленов от одной переменной с рациональными коэффициентами (на самом деле, значения этой переменной предполагаются целочисленными и неотрицательными). На этом множестве рассмотрим операцию, ставящую многочлену $f(x)$ (степени $n$) функцию $g(x)=\sum_{y = 0}^{x} f(a + by)$ (здесь $a$ и $b$ - параметры, являющиеся в моей ситуации неотрицательными целыми числами), которая является многочленом степени не выше $n + 1$ (потому, что этим свойством обладают суммы вида $\sum_{y = 0}^{x} y^k$ при $k \leqslant n$).

Являться-то является, но вычислять коэффициенты $g$ по коэффициентам $f$ в таком представлении, мягко говоря, неудобно.

Есть ли для этих целей базис поудобнее, чем последовательность степеней $\{x^k\}_{k \geqslant 0}$? Что скажете о базисе вида $\left\{\binom{x}{k}\right\}_{k \geqslant 0}$?

[Xaositect]

$x \choose k$ подойдет в случае $b = 1$. Это часто формулируют так: возьмем понижающиеся степени $x^{\underine{k}} = x(x - 1)\dots (x - k + 1)$, тогда $\sum\limits_{y = 0}^{x-1} y^{\underline{k}} = \frac{1}{k + 1} x^{\underline{k+1}}$, аналогично правилу интегрирования степеней. Для $b\neq 1$ надо будет поделить на подходящие степени $b$.

[MetaMorphy]

Про $b \neq 1$ не понял - что значит "поделить на подходящие степени"?

Формула, выражающая ${(a+bx)}^{\underline{k}}$ в базисе $\{x^{\underline{k}}\}_{k \geqslant 0}$, получается "лохматой" даже при $a=0$. Кстати, в моей ситуации $b > 1$ можно считать фиксированным (а вот $a$ плавает). Но операция применяется повторно, поэтому запихивать $b$ в базис - не вариант.

Ещё помучаюсь со всякими базисами, но, похоже, хоть "биномь", хоть "стирлингуй", всё равно будет хардкор ;)

[MetaMorphy]

Для мозоли глазу впишу, что получается в базисе обычных степеней.

Пусть $f(x) = \displaystyle\sum_{k = 0}^{d} f_k x^k$ и $g(x) = \displaystyle\sum_{y = 0}^{x} f(a + by) = \displaystyle\sum_{k = 0}^{d + 1}g_k x^k$. Тогда $g_0 = f(a)$ и

$\displaystyle\sum_{n = k}^{d} (-1)^{n - k} \binom{n + 1}{k} g_{n + 1} = b^k \displaystyle\sum_{n = k}^{d} \binom{n}{k} f_n a^{n - k} \quad (0 \leqslant k \leqslant d)$

Это даёт треугольную систему относительно $g_1, \ldots, g_{d + 1}$ и, соответственно, алгоритм квадратичной сложности по $d$, если арифметику коэффициентов считать константной по сложности.

Явная формула через числа Бернулли приводит к алгоритму кубической сложности. Есть куда стремиться?

[MetaMorphy]

В принципе, и так неплохо получается. Правда, мучиться с рациональными числами (несмотря на отличную разлагаемость знаменателей) не стал, вычисления в $p$-адиках оказались получше. Но пусть повисит, может вспомнится что-нибудь кому-нибудь.