ARC151 B. A < AP - Atcoder-myReflection-blueberry

ARC151 B. A < AP

Difficulty:1333

問題

長さ$ Nの順列$ Pが与えられる。各要素が$ 1以上$ M以下である長さ$ Nの数列$ Aのうち、$ A_i < A_{P_i} (1\leq i \leq N)を満たすものはいくつか。mod$ 998244353で数え上げよ。

解法

重要な事実として、数列として等しいものをのぞくと、辞書順で大きいものと小さいものの数はぴったり同じである。それをもとに考察していくと最終的に$ \frac{M^N-M^{連結成分数}}{2} となる。（連結成分数は、$ iから$ P_iに辺を張ったグラフの連結成分数）

実装

code:cpp

bool solve(){

LL(n,m);

vector<ll>p(n);cin >> p;

dsu uf(n);

rep(i,n)uf.merge(i,--pi);

mint ans = mint(m).pow(n);

ans -= mint(m).pow(uf.groups().size());

ans /= 2;

O(ans.val());

return false;

}