[AtCoder] ABC 179 E – Sequence Sum

2020年9月20日

問題

方針

シミュレーションすると分かると思いますが、\( A_i \) の値は周期的に遷移します。剰余は \( 0 \) から \( M – 1 \) までの値を取ります。したがって、周期的になる前の \( A_i \) の値を \( v_i \)、周期的な数列を \( w_i \) とします。

\( |v| \geq N \) のとき

このとき、\( v \) の先頭から \( N \) 個の和を計算します。

\( |v| < N \) のとき

\( N \leftarrow N – |v| \) と更新し、非負整数 \(t \) を

\[ t = \left \lfloor \dfrac{N}{|w|} \right \rfloor \]

とすると、\( t \) 回 \( w \) の列が現れるので、答えは、

\[ \sum_{i=1}^{|v|}v_i + t\sum_{i = 1}^{|w|}w_i + \sum_{i=1}^{N – t|w|}w_i\]

となります。

コード

感想

周期的な問題は以前出題されたことがありました。