JAPLJ https://blog.hatena.ne.jp/JAPLJ/ J * A * P * L * J https://japlj.hatenablog.com/ Algorithm いろいろ忘れないようにメモ✍しておくとよさそうなので書いておきます。 やること に対して 以下の奇数をすべて乗算した奇数階乗 (奇数に対する二重階乗)\begin{align} (2n-1)!! = 1 \cdot 3 \cdot 5 \cdot \cdots (2n-3)(2n-1) \end{align}を で高速に求めます。具体的には として 時間です。ここで の部分は多項式の乗算と平行移動 ( の係数から の係数を求める) にかかります。 やりかた ソースコードです。Petrozavodsk Camp の問題で出たんですがジャッジがどこか分からない……。いちおう の範囲で愚直なのと比較… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fjaplj.hatenablog.com%2Fentry%2F2018%2F04%2F07%2F132344" title="(2n-1)!! (奇数階乗) を mod 2^64 で求める - J * A * P * L * J" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=%20n%20%5Cgeq%201 Hatena Blog https://hatena.blog 2018-04-07 13:23:44 rich https://japlj.hatenablog.com/entry/2018/04/07/132344 1.0 100%