ABC478 F - Min-First Search
- サイト
- AtCoder
- コンテスト
- ABC478
- 問題
- F - Min-First Search
- 難易度
- 1588
頂点 の木 について、頂点 から始めて「訪問候補の集合 から番号が最小の頂点を取り出して訪問し、その未訪問の隣接頂点を に加える」ことを繰り返したときの訪問順を とします。順列 () が与えられるので、 となる木 の個数を で割った余りを求める問題です()。
以下、添字を 始まりにして とします。
各頂点の「親」を数える
Section titled “各頂点の「親」を数える”について、 を に加えたのは、 より先に訪問された隣接頂点です。木なので、 に隣接する頂点のうち より先に訪問されるものはちょうど 1 つで、これを の親 () と呼ぶことにします。木は「各 の親の選び方」と 1 対 1 に対応するので、条件を満たす親の選び方を数えればよいです。
を訪問した時点で が に入り、 は 番目に取り出されるまで に残ります。その間に取り出される はそのときの の最小値なので、すべて より小さくなければなりません。
そこで、 より前にある より大きい要素のうち最も後ろのものの位置を とします(なければ )。すると親の位置 の条件は
で、選び方は 通りです( 自身は大きくても、親として先に訪問されるので構いません)。
逆に、すべての についてこの範囲で親を選べば、 番目の時点で に残っている他の頂点 () は、親が より前にあるので条件から となり、 が最小として正しく取り出されます。したがって各 の選び方は独立で、答えは
です。
は「直前にある自分より大きい要素の位置」なので、
- 区間最大値のセグメント木で
min_leftを使って二分探索する() - 単調スタックの要領で、直前の大きい要素へのポインタをたどる(全体で )
のどちらでも求められます。
C++(セグメント木)
#include "ou-library/modint.hpp"#include "ou-library/segtree.hpp"#include "sh-library/base/all"using mint = modint998244353;
void solve() { LL(N); VL(Q, N); Q--; mint ans = 1; RMaxQ<ll> seg(Q); rep(i, 1, N) { ll j = seg.min_left(i, [&](ll x) { return x <= Q[i]; }); if (j) j--; ans *= i - j; } print(ans);}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve();}min_left(i, x <= Q[i]) で「 がすべて 以下になる最小の 」を求め、その 1 つ前が です。RMaxQ は区間最大値のセグメント木です。
使用ライブラリ:cpp_include@6c2f83f
cLay(ポインタをたどる)
#define MD 998244353ll@N,@Q[N],g[N],p;mint x=1;rep(i,1,N){p=i-1;while(p&&Q[p]<Q[i])p=g[p];g[i]=p;x*=i-p;}wt(x);g[i] に を記録しておき、 から始めて自分より小さい間は g をたどることで を求めています。 は最小なので、より大きい要素がなければ で止まります。