この記事は 【AtCoder】初中級者が解くべき過去問精選 100 問を緑色コーダーが C++ で解いてみた の子記事です。お読みになる前に親記事をご確認ください。
AtCoder Library の Modint にはべき乗を計算量 O(\log n) で計算するメンバ関数 pow があります。pow を使って問題を解きます。
70. NTL_1_B – べき乗
剰余演算の法が 10^9 + 7 で固定されているため、AtCoder Library の Modint の modint1000000007 (static_modint<1000000007>) を用います。m を整数型から modint1000000007 型に変換し、pow を使って n 乗を計算すれば答えになります。
計算量は O(\log n) = 10^2 程度です。
71. Square869120Contest #1 E – 散歩
街 c_{i – 1} から街 c_{i} への移動距離を都度計算する場合、全体の計算量は \Omega(N Q \log (\max_i a_i)) = 10^{12} 程度です。実行時間制限に違反しそうです。
累積和 を用いて街 1 から街 i への移動距離 \mathrm{cost}[i] を計算しておくと、街 c_{i – 1} から街 c_{i} への移動距離は以下の式を使って O(1) で計算できます。
\begin{aligned}
\mathrm{cost}[c_i] – \mathrm{cost}[c_{i – 1}]&& (c_i>c_{i – 1}) \\
\mathrm{cost}[c_{i – 1}] – \mathrm{cost}[c_{i}]&& (c_i<c_{i – 1}) \\
\end{aligned}
街 i – 1 から街 i を結ぶ道路の長さの計算に O(\log a_i) かかるため、累積和の計算量は O(N \log (\max_i a_i)) です。
全体の計算量は O(N \log (\max_i a_i) + Q) = 10^7 程度です。実行時間制限を満たして解答できます。
