(2n-1)!! (奇数階乗) を mod 2^64 で求める - J * A * P * L * J

いろいろ忘れないようにメモ✍しておくとよさそうなので書いておきます。 やること に対して 以下の奇数をすべて乗算した奇数階乗 (奇数に対する二重階乗) \begin{align} (2n-1)!! = 1 \cdot 3 \cdot 5 \cdot \cdots (2n-3)(2n-1) \end{align} を で高速に求めます。具体的には として 時間です。 ここで の部分は多項式の乗算と平行移動 ( の係数から の係数を求める) にかかります。 やりかた ソースコードです。Petrozavodsk Camp の問題で出たんですがジャッジがどこか分からない……。いちおう の範囲で愚直なのと比較して verify してあります。 uint64_t oddfact(uint64_t n) { if (n == 0) return 1; static uint64_t comb64[64]