Yukicoder 502 階乗を計算するだけ
n (0≦n≦10^18) のとき、n! (mod 10^9 + 7) を計算せよという問題。
普通にやるとn!の計算はO(n)かかる。nがmodの値(=10^9+7)以上のときは恒等的に0であるが、それでもO(10^9)で間に合わない。ちょっとしたテクニックとして、nがmodに近いときはウィルソンの定理 (p - 1)! ≡ -1 を使うと多少早くなるのだが、それでもオーダーが一桁減るか減らないかでどうしようもない。
結局解けなかったので解説を見ると、10^6 ごとの計算結果を10^3個保存しておき、途中から計算を始めるらしい(要は埋め込み)。処理計算量を空間計算量に置き換えるテクはよくあるんだがすっかり忘れてた。
