[問題案] sum_of_exponential_times_polynomial_limit

[yosupo06]

f: 高々 d 次の多項式 (given) \sum_{0<=i<INF} a^i f(i) を求めるやつ (-1 < a < 1 な有理数ということにして結果を mod とかで)

O(d^2) か，単項式にして O(d log d) をするか

Originally posted by @hos-lyric in https://github.com/yosupo06/library-checker-problems/issues/3#issuecomment-533812384

[yosupo06]

98と何らかの関係性があるんだろうということだけはわかる

[hos-lyric]

動機：(1/2)^0 0^3 + (1/2)^1 1^3 + (1/2)^2 2^3 + ... みたいな極限を求めるやつ，毎回手計算するのつらくないですか 問題例：https://atcoder.jp/contests/agc038/tasks/agc038_e 文献：しらない 方法：係数が Eulerian number になるのでどうにかする

98 との関係性を何も考えずに書いたけど，同じようにやればこれも f(0), ..., f(d) 経由で求まる気がしてきてしまったな

[ghost]

b_i := a^i f(i) とおくと、b_0 + b_1 x + b_2 x^2 + ... の母関数は g(x) / (1 - ax)^{d+1} （ただし、g(x) = (1 - ax)^{d+1} (b_0 + b_1 x + b_2 x^2 + ... + b_d * x^d) mod x^{d+1}）で、g(1) / (1-a)^{d+1} を計算すれば求まる感じでしょうか。

[hos-lyric]

頭が足りなくて母関数からの導出が苦手です min-25 さんのブログの式から単に n を無限に飛ばして

(1 / (1-a)^(d+1)) \sum_{1<=i<=d+1} (C(d+1, i) (-a)^(d + 1 - i) (a^0 f(0) + ... + a^(i-1) f(i-1))

を得てこれなら O(d) で計算できます．もっと綺麗に書ける気はあまりしないけどわかりません

[hos-lyric]

問題名: (ここに #98 のタイトルを入れる) Limit (???)

問題概要

\sum_{i=0}^{\infty} r^i i^d を mod 998244353 で求めよ r は -1 < r < 1 なる有理数 (入力では mod 998244353 で与えられる)

入力

d r

出力

answer

制約

• 0 <= d <= 10^7
• 0 <= r < 998244353

---

O(d log log d) くらい こっちができると #98 が楽になったりもする

[hos-lyric]

r == 1 (mod 998244353) がやばい (つまり，r = 1/998244354 とか r = -98244353/100000000 とか) (どうしよう) (r = p/q, 0 <= p < q < 998244353 とかで書いといた方が綺麗な可能性もある)

[yosupo06]

あれ、r == 1だと一体何が起きてるんだろう mod 998244353では定義できない有理数に収束するのかな

[yosupo06]

r != 1って制約を足せば良さそう(0 <= p < q < 998244353)って要するにr != 1と同値なはずで、わざわざ複雑にしてる感(設定としては自然だけど)

[yosupo06]

いや(0 <= p < q < 998244353)でもq = p^-1 mod rにすればr == 1になるのでは？

→　なりません　思考能力の欠如

[hos-lyric]

r == 1 (mod 998244353) だと分母に 998244353 が入る有理数に収束しますね ……と思ってたんですが自信がない (mod 2 だと \sum (1/3)^i i^4 = 15, \sum (1/5)^i i^4 = 285/128 などのように分母に 2 が来るかどうかが r mod 2 だけで決まらないという現象が起きることに気づいた．mod 2 だけな気もするが……)

(答えは (r の有理式) / (1-r)^(d+1) なので) r != 1 (mod 998244353) なら well-defined です といったことを多少書いて問題文を複雑にさせるか，分子分母を与えてわざわざ割り算をさせるかですね．まあ r を与えるやつでいっか～

[yosupo06]

r!=1の方にしたいです(2/(MOD+1))とか、真にrのほうでしか与えられない入力があるし

[cai-lw]

Why is $d$ so large? I can't even FFT (without pain in ass) with $d=10^7$.

The most natural way to solve this is finding Eulerian polynomial in O(dlogd) which is fast enough for competitive programming purposes, and also seems to be the intended solution at the beginning. I don't think one can come up with the O(d) solution without reading that one specific blog mentioned here.

[maspypy]

98と何らかの関係性があるんだろうということだけはわかる

an = \sum{i=0}^n として、どちらも、 A(x) = f(x) / (1-rx)^{d+1}(1-x) （f は多項式） の形の母関数を持ち、違いは

• 大きな n に対して a_n を求めよ
• \lim a_n を求めよ

共通ルートの解法として、A(x) = g(x) / (1-rx)^{d+1} + c / (1-x) という部分分数分解の c を得るというものがありました。c が求まれば、

• a_n - c は、分母 (1-rx)^{d+1} を持つので r^n * (poly) の形
• 大きな n に対する計算は r^n × (多項式補間) + c
• limit は c

ので、特殊なタイプの部分分数分解を行うライブラリ問題という見方もできそう。