\(A\) はサイズ \(N\) のリスト． このとき， \(mex(A) \leq N\) となる． つまり，答えの候補が小さい． 実際 \(A\) の元 \(e\) のうち， \(e < 0, \ N < e\) は取り除いても mex は変わらない． また， 調和級数の様な見積もりで \(O(N log N)\) しか候補が無い．
実装
\(A\) の値は変化するが，変化した後に \(0 \leq A_{i} \leq N\) となる範囲だけ考えればよい． とくに負になる場合に注意．
\(0 \leq A_{i} + (i+1)(x+1) \leq N\) となる \(x \in M\) を求めると， \begin{allign*} \frac{-A_{i}}{i+1} \leq x+1 \leq \frac{N-A_{i}}{i+1} and \\ 1 \leq x+1 \leq M \begin{allign*} となる．負の場合にも対応した，商の ceil を作っておくと， 他の問題でも使えて楽．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
template<typename T> T ceil(T a, T b);
template<typename T> T floor(T a, T b);
template<typename T>
// args : a and b are integers s.t. b \neq 0
// return : ceil(\frac{a}{b})
T ceil(T a, T b){
assert(b != T(0));
if(b < T(0)){
a *= T(-1);
b *= T(-1);
}
if(a >= T(0)){
return (a + (b-T(1)))/b;
}else{
assert(a <= T(0) && b > T(0));
return - floor(-a, b);
}
}
// args : a and b are integers s.t. b \neq 0
// return : floor(\frac{a}{b})
template<typename T>
T floor(T a, T b){
assert(b != T(0));
if(b < T(0)){
a *= T(-1);
b *= T(-1);
}
if(a >= T(0) && b > T(0)){
return a/b;
}else{
assert(a <= T(0) && b > T(0));
return - ceil(-a, b);
}
}
int main() {
ll n, m ;
cin >> n >> m;
vll a(n); rep(i,n) { cin >> a[i]; }
vvll v(m);
rep1(i,n){
ll l = 1, r = m;
chmax(l, ceil(-a[i-1], i));
chmin(r, floor(n-a[i-1], i));
r++;
srep(x,l,r){
ll now = a[i-1]+i*x;
if(in(now, n+1)) v[x-1].push_back(now);
}
}
for(auto b: v){
int sz = b.size();
for(auto i : b) if(0 <= i && i <= sz) e[i] = true;
int ans = 0;
while(e[ans]) ans++;
cout << ans << endl;
}
return 0;
}
