ABC156の解説です。
36:51全完で、12位を取って最高記録を更新しました。
では、解説に入ります。
A問題
問題文解読ゲーです。
$N$ が $10$ 以上の場合とそうでない場合に分けるか、$max$ で適当に処理するかしましょう。
それでもこれはB問題相当くらいあると思うのですが…
B問題
結論から言えば、${\rm ceil}(\log_K N)$ を求めればいいのですが、$N$ を $K$ で順々に割っていくのが一番楽で早いです。
C問題
集会をする位置を全探索します。
$X_i$ の制約を考えると、集会は $1$ 以上 $100$ 以下のどこかで開かれるので、これを全部試せばよいです。
D問題
$1$ 以上 $n$ 以下の、 $a,b$ 以外のすべての整数 $i$ について ${}_n\mathrm{C} _i$ を計算して、その総和を求めます。
$N$ の制約は大きいので、このままだと間に合いません。
\sum_{i=0}^{N} {}_N \mathrm{C} _i=2^N
が成り立つことはあまりにも有名で、これは前提知識となります。
結局、$2^N$ から ${}_N\mathrm{C} _a$ と ${}_N\mathrm{C} _b$ と $1$ （0本の場合）を引いたものが答えです。
E問題
D問題に引き続き、組み合わせの問題です。
$n$ と $k$ の条件を満たすような人数の組み合わせは、どのような性質があるでしょうか。
結局のところ、条件を満たすのは、$0$ 人の部屋が $k$ 部屋以下であることと同値です。
$k\geq 2$ の条件がないと実はこれは成り立ちませんが、簡単に証明できるので省略します。
$0$ 人の部屋の個数を $i$ 個と決めたとすると、この時の組み合わせの個数は、人の入る部屋への人の入り方と、人の入る部屋の集合の選び方を考えて、
{}_{i} \mathrm{H} _{N-i}\cdot{}_{n} \mathrm{C}_i={}_{n-1} \mathrm{C}_i\cdot{}_{n} \mathrm{C}_i
となるので、これを $i$ が $min(n,k+1)$ 未満になるまで計算して加算すればよいです。
F問題
それぞれのクエリで構成される数列は、$x_i$ を初項として、差が $d$ の各要素の繰り返しによって周期的に変化する数列です。
それぞれのクエリについて、$d$ の各要素と$x_j$ は、$\bmod{m_j}$ で考えて問題ありません。
$(a_j \bmod{m_i})<(a_{j+1} \bmod{m_i})$ となる $j$ の個数は、$(a_j \bmod{m_i})\geq(a_{j+1} \bmod{m_i})$ とならない $j$ の個数を $n_i-1$ から引いたものに他なりません。
これを求めることで答えを引き算で求めることを考えます。
まず、$(a_j \bmod{m_i})=(a_{j+1} \bmod{m_i})$ となる場合は、$d$ の各要素が加算されるときにそれが $0$ かどうか考えればいいので、周期性を利用すれば簡単に求められます。
$(a_j \bmod{m_i})>(a_{j+1} \bmod{m_i})$ となる時には、modの世界で繰り上がりが起きている、と解釈して、最初から最後までで繰り上がりが何回起こるか計算します。$d$ の各要素について先にmodをとっておき、ここでも周期性を利用して初項からmodの値がいくら増えるかわかれば、繰り上がりの回数も計算できます。
こうして、$(a_j \bmod{m_i})\geq(a_{j+1} \bmod{m_i})$ となる $j$ の個数が求められたので、答えが求まりました。
計算量は各回のクエリで $O(k)$ で、全体で $O(kq)$ です。
おわりに
今回は、前回とは違って結構な早解きセットでした。
DとEで数学力が試されたのもありましたが、簡単めな回だったと思います。
Fは、とてもABCらしい問題だと思いました。
ではまた。