# Pow of Formal Power Series (Sparse) (チラ裏)

## 定義まわり

https://maspypy.com/%E5%A4%9A%E9%A0%85%E5%BC%8F%E3%83%BB%E5%BD%A2%E5%BC%8F%E7%9A%84%E3%81%B9%E3%81%8D%E7%B4%9A%E6%95%B0-%EF%BC%88%E8%A3%9C%E8%B6%B3%EF%BC%89%E5%AE%9A%E7%BE%A9%E3%82%84%E5%BC%8F%E5%A4%89%E5%BD%A2

陽に使うやつ: 積, 微分

## 目標

https://judge.yosupo.jp/problem/pow_of_formal_power_series_sparse

非零な係数が $K$ 個しか無い $f\in \mathbb{F}_{998244353}[[x]]$ と非負整数$M$に対して$f^M$を$0$次$\cdots$$N$次まで求めたい

- $0\ \le\ K\ \le\ 10$
- $0\ \le\ M\ \le\ 10^{18}$
- $0\ \le\ N\ \le\ 10^{6}$

## やる

https://github.com/yosupo06/library-checker-problems/issues/767

$F = f^M$ として、等式$fF' = MFf'$が成り立つことが確認できる。

$F_0 = f_0^M$

定数項

左辺・・・ $f_0F'_0$
右辺・・・ $MF_0f'_0 = MF_0f_1$

$f_0\ \ne\ 0$ ならば $F'_0$ が計算できて、$F_1 = F'_0$ と分かる。

1次の項

左辺・・・ $f_0F'_1 + f_1F'_0$
右辺・・・ $M(F_1f'_0 + F_0f'_1) = M(F_1f_1 + \frac{1}{2}F_0f_2)$

$F_0, F_1$ が既知なら $F'_1$ が計算できて、 $F_2 = \frac{1}{2}F'_1$ と分かる。

2次の項

左辺・・・ $f_0F'_2 + f_1F'_1 + f_2F'_0$
右辺・・・ $M(F_2f_1 + \frac{1}{2}F_1f_2 + \frac{1}{3}F_0f_3)$

$F_3 = \frac{1}{3}F'_2$
....

と、 $f_0\ \ne\ 0$ ならば $[x^n]F$ が $n$ の小さい順にどんどん求まっていく

毎回非零の係数 $a_0, a_1, \dots, a_K$を舐めれば $O(NK)$ でできる... ハズ

- 線形の逆元列挙とかが前計算で必要かな

## $f_0 = 0$ の時

$i_0$ 項左シフトした場合で考えれば良い..ハズ

$f^M$ の最初の非零な項は $[x^{Mi_0}]f^M$

## 出題例

- https://atcoder.jp/contests/abc276/tasks/abc276_g
- https://onlinejudge.u-aizu.ac.jp/problems/3361
- imosでTLEするの助けてくれになった。助けてくれ