Closed maspypy closed 4 years ago
(任意) 問題ID: {} 問題名: {Polynomial Taylor Shift}
想定アルゴリズム: FFT (NTT) 参考資料: ・調べた範囲では次が初出?https://pdfs.semanticscholar.org/2ab5/44691c7145b4ae58481a0f60f69e861b4949.pdf?_ga=2.268358734.1196800475.1586024955-1317097338.1586024955 ・AGCで登場(多項式と言ってはいないが) https://atcoder.jp/contests/agc005/tasks/agc005_f ・りすじろうさん https://twitter.com/risujiroh/status/1215710785000751104?s=20
注意: 数値計算では精度上あまり使えないらしい?(階乗をかけてスケール変えまくるし?) なお、形式的べき級数ではなく多項式に対する操作です。
多項式 $f(x)=\sum a_ix^i$ と定数 $c$ が与えられる。$f(x+c)$ を計算。
$N$ $c$ $a_0, a_1, a_2, \ldots, a_N$
$b_0, b_1, b_2, \ldots, b_N$
$1\leqq N\leqq 524288$, $0\leq c, a_i < 998244353$.
階乗をかけたり逆順にしたりしながら FFT 1回やるだけです。 既に3回くらい経験したのでライブラリにしてある方が便利だと思い、issue立て。 ついでに、yosupo judge作問初挑戦をしていこうかと。やり方調べながら今月中目標で進めてみます。
一般的な操作だと思いますし、いいと思います!
(任意) 問題ID: {} 問題名: {Polynomial Taylor Shift}
想定アルゴリズム: FFT (NTT) 参考資料: ・調べた範囲では次が初出?https://pdfs.semanticscholar.org/2ab5/44691c7145b4ae58481a0f60f69e861b4949.pdf?_ga=2.268358734.1196800475.1586024955-1317097338.1586024955 ・AGCで登場(多項式と言ってはいないが) https://atcoder.jp/contests/agc005/tasks/agc005_f ・りすじろうさん https://twitter.com/risujiroh/status/1215710785000751104?s=20
注意: 数値計算では精度上あまり使えないらしい?(階乗をかけてスケール変えまくるし?) なお、形式的べき級数ではなく多項式に対する操作です。
問題概要
多項式 $f(x)=\sum a_ix^i$ と定数 $c$ が与えられる。$f(x+c)$ を計算。
入力
$N$ $c$ $a_0, a_1, a_2, \ldots, a_N$
出力
$b_0, b_1, b_2, \ldots, b_N$
制約
$1\leqq N\leqq 524288$, $0\leq c, a_i < 998244353$.