Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Regular Contest 151 B問題 A<AP

AtCoder ARC151 ARC B問題 500 pts

問題

提出解答

問題の概要

$(1,2, \dots, N)$ の順列 $P$ が与えられる.

以下の条件を共に満たす長さ $N$ の整数列 $A=(A_1, \dots, A_N)$ の数を求めよ.

各項は $1$ 以上 $M$ 以下の整数
$A':=(A_{P_1}, \dots, A_{P_N})$ とすると, $A$ は $A'$ より辞書順で小さい.

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq M \leq 10^9$
$P$ は $(1,2, \dots, N)$ の順列.

解法

各項が $1$ 以上 $M$ 以下である長さ $N$ の整数列全体の集合 $\mathcal{X}$ とする.

$\mathcal{X}$ の部分集合 $\mathcal{S}, \mathcal{T}, \mathcal{U}$ を

$\mathcal{S}:=\{A \in \mathcal{X} \mid A \lt A' \}$
$\mathcal{T}:=\{A \in \mathcal{X} \mid A =A' \}$
$\mathcal{U}:=\{A \in \mathcal{X} \mid A \gt A' \}$

とする. このとき, $\mathcal{S}, \mathcal{T}, \mathcal{U}$ は $\mathcal{X}$ の分割になることに注意する.

求めるべきは $\# \mathcal{S}$ である. ここで, $\mathcal{S}$ と $\mathcal{U}$ の間には次のような全単射がある.

$\varphi: \mathcal{S} \to \mathcal{U}; \quad A=(A_i)_{i=1}^N \mapsto (M+1-A_i)_{i=1}^N$

よって, $\# \mathcal{S}=\# \mathcal{U}$ である.

以上から, $\# \mathcal{S}+\# \mathcal{T}+\# \mathcal{U}=\# \mathcal{X}=M^N, \# \mathcal{S}=\# \mathcal{U}$ より, $\# \mathcal{T}$ さえ求められれば,

$\# \mathcal{S}=\dfrac{M^N-\# \mathcal{T}}{2}$

より求められることができる.

$A \in \mathcal{X}$ とする. $A \in \mathcal{T}$ であることの必要十分条件は

$A_1=A_{P_1}$
$A_2=A_{P_2}$
$\vdots$
$A_N=A_{P_N}$

である. この $N$ 個の等式をまとめると, $\{1,2, \dots, N\}$ の分割を $\{i_{j,1}, \dots, i_{j,k_j} \} \quad (j=1,2, \dots, K)$ としたとき,

$A_{i_{j,1}}=\dots=A_{i_{j,k_j}} \quad (j=1,2, \dots, K)$

である.

よって, $A_{i_{1,1}}, \dots, A_{i_{K,1}}$ によって $A \in \mathcal{T}$ を決定できるので, $\# \mathcal{T}=M^K$ である.

したがって,

$\# \mathcal{S}=\dfrac{M^N-\# \mathcal{T}}{2}=\dfrac{M^N-M^K}{2}$

である.

$\{1,2, \dots, N\}$ の分割を $\{i_{j,1}, \dots, i_{j,k_j} \} \quad (j=1,2, \dots, K)$ は以下で定義される無向グラフ $G=(V,E)$ の連結成分に対応する.

$V:=\{1,2, \dots, N\}$
$E:=\{i P_i \mid i=1,2, \dots, N\}$

よって, このグラフ $G$ における連結成分の個数を求めることになり, 計算量は $O(N)$ 時間で求めることが出来る.