ABC156

全体

5完。立ち回りも特に悪くなかった。単純に解くスピードが遅い。

D-Bouquet

nCkはO(k)でできることに気付くのに10分くらいかかった気がする...。

E-Roaming

重複組み合わせ、少し焦って計算ミスったりしたのが良くない。割とすぐ気づけたのは良かったから、詰めを冷静にしたい。

F-Modularness

コンテスト中に解けず...。
dの要素を各クエリでmod mに置き換えても間に合う。
1) a_i mod m = a_i+1 mod mのとき
d_{i mod k} = 0
「d_i=0がn項のうち何回現れるか」をカウントすれば良い。

2)a_i mod m > a_i+1 mod mのとき
m <= a_i+1 < a_i+m
である。つまり、mで割ったときの商がちょうど1つ増える。「商が全体でいくつ増えるか」が分かればよく、aは単調増加だから、a_n-1の商とa₀の商を比較すれば良い。

数えたいものが直接数えにくいときは、全体から「数えたいものの条件を満たさないもの」を引く。これは典型的な「余事象」の発想であり、数学と少し見た目が違っても頭に置いておくべきだった。