April Challenge 2018

Chef 側の解説がまだ出てないので、それ読んで思うものがあったら更新します。

CHEFAT:
この制約なら SIMD O(n^2) 通る。そうは言っても 2 ケースほど TLE になってしまったので、平方分割＋遅延評価で平均的に速くなるようにした。
多くの提出は $\log(1-x)=-x-x^2/2-x^3/3-...-x^{100}/100$ で近似してる。
最後に exp とったときの誤差は大丈夫なのかなと思ったけど $e^{x+\epsilon} - e^x \approx \epsilon e^x$ なので大丈夫そう。

SSPLD:
固有多項式を埋め込む（そんなに次数は大きくない）。具体値を埋め込むとコード長制限に引っかかるため実行時に計算。多項式乗算・剰余は FFT で高速にやらないと厳しい。多くの提出は hadamard transform を使ってるように見える。確かにできそう。

11 変数多項式 f(x,y0,...,y9) を FFT する感じ？f(x,y0,...,y9) にある多項式を掛けることで遷移を表現できる（下の桁から値を決めていくわけだが、遷移関数は周期的、周期は 10^k mod s に依存）。そして S×2×2×…×2 の FFT をしておけば係数の積から値の積に変換できて、解ける。（S に関して言うと 2 冪じゃないから FFT じゃないけど（高速ではない））→よく考えたらNTTなのでSでできない。いや体拡大でできるかもしれないけど、そうではないんだろう。