ダブリングライブラリ
ダブリングを行うライブラリを書きました．自分用のメモです． できること その1 $f : [0, N) \to [0, N)$ が与えられた時， $f^{r}(i)$ を，$r \in [0, R]$ と $i \in [0, N)$ に対して計算する． 典型的には: $N$ は $10^5$ くらい，$R$ は $10^{18}$ くらい，または $N$ も $R$ も $10^5$ くらいだが，何回も (たとえば $10^5$回くらい) 計算する その2 上の $f$ の他に，モノイド $(M, \oplus)$ と $m: [0, N) \to M$ が与えられて， $r, i$ に対して $\bigoplus_{k = 0}^{r} m(f^{k}(i))$ を計算する． 使用例 その1 ll R = 100000, N = 100000; auto f = [&](ll i) -> ll { return i * i % N; }; DoublingFRel d(R, N, f); ll r = 12345, i = 54321; cout << d....