$\sum_{i}a^i f(i)$
(fps/sum-of-exponential-times-poly.hpp)
$\sum_{i}a^i f(i)$
問題
$k$次多項式$f(n)$に$f(0),f(1),\ldots,f(k)$を代入したものが与えられる。$\sum_{0\leq i \lt n}f(i)a^i$を求めよ。
出題例(codechef)
参考文献(Min氏のブログ)
概要
この問題は$\mathrm{mod}$を素数としたとき計算量$\mathrm{O}(N + \log \mathrm{mod})$で解くことが出来る。
以下の説明では、$f(t)$が$k$次の多項式であるとき、$f(t)$の母関数は$\frac{F(x)}{(1-x)^{k+1}}$と表せる事実を利用する。
(証明はニュートン基底$n_i(t)=t(t-1)\cdots(t-i+1)$の母関数が$\frac{i!x^i}{(1-x)^{i+1}}$と表されることが帰納的に示せることと、$f(t)$は$n_0(t)\ldots n_k(t)$の線形和で表せることから従う。)
数列$f(0)a^0, f(1)a^1, \ldots$の母関数は$k$次以下の多項式$G(x)$を用いて$\frac{G(x)}{(1-ax)^{k+1}}$と表せる。この時、求めたいものは
\[[x^{n-1}]\left(\frac{1}{1-x}\cdot \frac{G(x)}{(1-ax)^{k+1}}\right)\]
となる。上の式は定数$c$と$k$次以下の多項式$S(x)$を用いて
\[\frac{G(x)}{(1-x)(1-ax)^{k+1}}=\frac{c}{1-x}+\frac{S(x)}{(1-ax)^{k+1}}\]
と変形できるので、解は$k$次以下の多項式$t(n)$を用いて$c+a^nt(n)$と表せることがわかる。
次に$c$を具体的に求める。$c,G,S$の間には
\[G(x)=c(1-ax)^{k+1}+S(x)(1-x)\]
が成り立つ。多項式なので両辺に$x=1$を代入してもよく、
\[G(1)=c(1-a)^{k+1}\]
を得るので$G(1)$を求めればよい。$G(1)$は
\[G(x) = \left((1-ax)^{k+1}\sum_{i=0}^k f(i)(ax)^i \mod x^{k+1}\right)\]
の右辺を累積和と階乗の前計算を使って$\mathrm{O}(k)$で計算できる。
$c$が計算できたので、あとは多項式補間を使えば答えが求まる。具体的には、
\[t(i) = a^{-n}\cdot\left(-c + \sum_{j=0}^i f(i)a^i \right)\]
とおいて$t(0),t(1)\ldots t(k)$を計算した後、ラグランジュ補間で$t(n-1)$を$\mathrm{O}(k)$で計算すればよい。
(注:この解法では$a$と$1-a$の逆元が必要なため、$a=0,a=1$の時は場合分けして別に実装する。)
Depends on
Verified with
Code
Back to top page