コーナーケース

無限通りになる場合を考えてみます。

入力の \(c_i\) がすべて同じである場合、無限通りです。これは、 \(a_N, a_N+1, \cdots,\) がすべて条件を満たすからです。

逆に、それ以外の場合は無限通りではありません。たとえば \(a_1\) が色 \(1\) で塗られており、 \(a_2\) が色 \(2\) で塗られているとき、 \(M \ge a_2\) だと矛盾します。これにより、無限通りになりません。

また、 \(a_i<a_j<a_k\) で \(c_i\ne c_j, c_i=c_k\) があるとき、 \(0\) 通りです。これを排除すると、実は見るべきペアは \((i,i+1)\) の \(N-1\) 個だけになります。

ペアについて…

\(c_i \ne c_{i+1}\) なら、\(M\) によって \(a_i\) と \(a_{i+1}\) の間が分断される必要があります。すなわち、妥当な \(M\) 全体の集合を \(S\) とすると、 \(S\) は正整数 \(k\) が存在して \(a_i \le kM < a_{i+1}\) となるもの全体となります。 \(k\) を固定すると、

\[S = \bigcup_{k\ge 1} \left[ \left\lceil \frac{a_i}{k} \right\rceil, \left\lceil \frac{a_{i+1}}{k} \right\rceil \right)\]

となります。 \(c_i = c_{i+1}\) なら、逆に \(a_i\) と \(a_{i+1}\) の間が分断されてはいけません。妥当な \(M\) 全体の集合は、先ほどの \(S\) の補集合、すなわち \(\mathbb{N} \backslash S\) となります。

計算量

\(k=1,2,\cdots, \) と固定すると間に合いません。しかし、 floor div のテクニックが使えます。 \(\{\lfloor a/i \rfloor \mid i \ge 1\}\) の集合の要素数が \(O(\sqrt{a})\) 個であることを利用すると、先ほどの集合は区間の和集合として \(O(\sqrt{\max a})\) 時間で列挙できます。

このテクニックを知らない方は Library Checker の Enumerate Quotient や ABC230-E Fraction Floor Sum を参照ください。 https://judge.yosupo.jp/problem/enumerate_quotients https://atcoder.jp/contests/abc230/tasks/abc230_e

最後にそれらの共通部分の大きさを求めるので、 \(O(N \sqrt{\max a} \log(N \sqrt{\max a}))\) 時間で解けます。

より軽い実装

区間の端点の候補は \(\lceil a_i / K\rceil\) だけなので、それらを全部列挙してから、昇順に見ていって、それぞれ条件を満たすか \(O(N)\) で判定することで解けます。

計算量は \(O(N \sqrt{\max a} (\log(N \sqrt{\max a}) + N))\) 時間、工夫をすれば \(O(N^2 \sqrt{\max a})\) 時間になると思います。