はじめに

AGC036A を解くときに詰まった記録です。

世の中には美しい解法を示すブログが沢山あります。
しかし私は、間違いからの脱却方法も欲しいのです。

間違い

最初に提出したコードでは、01-13.txt のみが通りませんでした。

1 つのケースのみ通らないので、極端な入力を考えれば良いはずだと考えます。
S が上限値の 10^9 を取るとき、 y2 は 0 になるべきなのに、上記コードでは 10^9 になってしまうことに気が付きました。

修正

y2 を導出する部分のコードを修正して提出。

教訓

python を使うことが多かったので、mod の計算を自分で正しくできていなかったのが原因。
負の値 x の mod を取るときは (x % mod + mod) % mod
一回間違えれば次は間違わないはず。