noshi91のメモ

データ構造のある風景

Universal Cup. Stage 10: Zhejiang. A Atcoder Problem

アルゴリズム

公式解説と違う方法で解いたのだが、その時に使った式変形が面白かったので紹介。

いくらかの計算をすると、次の問題に帰着される。

W 個の非負整数組 (a _ i, b _ i, c _ i) が与えられる。 これらは全て a _ i + b _ i = M を満たす。

\displaystyle \sum _ {i = 1} ^ {W} \frac{c _ i}{(1 - x) ^ {a _ i} (1 + x) ^ {b _ i}} の先頭 N 項を \bmod 998244353 で計算せよ。

  • W \leq 60
  • M \leq 10 ^ {18}
  • N \leq 10 ^ 5

追記

もっと簡単な方法が紹介されていた。 \displaystyle F(x) := \frac{c _ i}{(1 - x) ^ {a _ i} (1 + x) ^ {b _ i}} とすると、 F'(x) = \left ( - \frac{a _ i}{1 - x} + \frac{b _ i}{1 + x} \right ) F(x) である。 分母を払うと F(x) の係数の間に漸化式があることが分かるので、それに沿って計算すれば O(N) である (疎な微分方程式の解)。 これを W 回行って足し合わせればよい。

これに気付かなかったの恥ずかしい...

追記終わり

\displaystyle \sum _ {i = 1} ^ {W} \frac{c _ i}{(1 - x) ^ {a _ i} (1 + x) ^ {b _ i}} = \frac{1}{(1 + x) ^ M} \sum _ {i = 1} ^ {W} c _ i \left ( \frac{1 + x}{1 - x} \right ) ^ {a _ i} であるから、以下の問題が解ければよい。

多項式 f は高々 W 個の非零な係数を持つ。 \displaystyle f \left ( \frac{1 + x}{1 - x} \right ) の先頭 N 項を求めよ。

まず f(1 + 2t) の先頭 N 項を計算し、次に \displaystyle t = \frac{x}{1 - x} を代入することで計算する。 f(1 + 2t) の計算を先頭 N 項で打ち切ることは、 \displaystyle \frac{x}{1 - x} の定数項が 0 であることから正当化される。 f(1 + 2t) は二項定理を用いて \mathrm{O}(NW) で計算できるから、残るのは以下のような問題である。

N 次の多項式 g が与えられる。 \displaystyle g \left ( \frac{x}{1 - x} \right ) の先頭 N 項を計算せよ。

これは以下のような手順で計算できる。

  1. \displaystyle \mathrm{rev}(g)(t) = t ^ n g \left ( t ^ {-1} \right ) を計算する。単に多項式の係数を左右反転するだけでよい。
  2. t = x - 1 を代入し、 \displaystyle (x - 1) ^ n g \left ( \frac{1}{x - 1} \right ) を得る。(taylor shift)
  3. これの係数を再び反転させ、 \displaystyle x ^ n \left ( x ^ {-1} - 1 \right ) ^ n g \left ( \frac{1}{ x ^ {-1} - 1 } \right ) = (1 - x) ^ n g \left ( \frac{x}{1 - x} \right ) を得る。
  4. (1 - x) ^ n で割る。

時間計算量は \mathrm{O}(NW + N \log(N) ) である。

後半部分はこの記事と同じ計算をしている。 [多項式・形式的べき級数] 高速に計算できるものたち | maspyのHP 指数部分の和が一定というと使いどころが分かりづらいが、一般に 1 次の有理式の代入が \mathrm{O}(N \log(N) ) でできると言い換えると見た目は良いかもしれない。