Official

B - A < AP Editorial by leaf1415


以下、数列と言うときは、\(1\) 以上の \(M\) 以下の整数からなる長さ \(N\) の数列を指すこととします。 また、数列 \(A\) に対して、\(A' := (A_{P_1}, A_{P_2}, \ldots, A_{P_N})\) とします。

数列 \(A\) は全部で \(M^N\) 個あります。\(A = A'\) を満たす \(A\) の個数を \(X\) とおくと、 辞書順で \(A' \lt A\) である \(A\) の個数と、辞書順で \(A' \gt A\) である \(A\) の個数は、対称性から等しいため、本問題の答えは \((M^N - X) / 2\) です。

\(X\) はすべての \(i = 1, 2, \ldots, N\)\(A_i = A_{P_i}\) を満たす数列 \(A\) の個数なので、\(\lbrace 1, 2, \ldots, N \rbrace\) を頂点集合とし各 \(i = 1, 2, \ldots, N\) について無向辺 \(\lbrace i, P_i \rbrace\) を張った無向グラフ \(G\) を考えると、 \(X\)\(G\) の各連結成分に \(1\) 以上 \(M\) 以下の整数を対応させる方法の個数と等しいです。 よって、\(G\) の連結成分の個数を \(C\) とすると、\(X =M^C\) です。

以上より、本問題の答えは \((M^N - M^C)/2\) です。

posted:
last update: