I - Left Equals Right 解説
by 
number_cat
\(S=A_1+\cdots+A_N\) とします。 \(S\) の偶奇で場合分けをします。
$S$ が奇数のとき
両辺で偶奇が一致しないため、条件を満たす順列は存在しません。よって答えは \(0\) です。
$S$ が偶数のとき
\(X=A_{P_1}+\dots+A_{P_i}=A_{P_{i+1}}+\dots+A_{P_N}\) と置いたとき、 \(S=2X\) が成り立つので \(X\) の値が求まります。
条件を満たす順列に対して \(A_{P_1}+\dots+A_{P_i}=A_{P_{i+1}}+\dots+A_{P_N}\) を満たす \(i\) はちょうど \(1\) つ存在します。
そのため、 \(i=1,2,\dots,N-1\) について \(A_{P_1}+\dots+A_{P_i}=A_{P_{i+1}}+\dots+A_{P_N}\) を満たす順列 \(P\) の総数を \(C_i\) としたとき、答えは \(C_1+C_2+\dots+C_{N-1}\) です。
\(C_i\) は、要素数 \(i\) の \(\{1,\cdots,N\}\) の部分集合 \(T\) であって \(\sum_{x \in T} A_x=X\) を満たすものの総数に \(i!(N-i)!\) をかけたものに等しいです。
理由
条件を満たす部分集合 \(T=\{x_1,x_2,\dots,x_i\}\) に対して、順列 \((P_1,P_2,\dots,P_N)\) は \(\{P_1,P_2,\dots,P_i\}\) が \(\{x_1,x_2,\dots,x_i\}\) と集合として等しくなるように定めたときに問題の条件を満たし、このような \(P\) は \(i!(N-i)!\) 通り存在する。（ここで同じ順列が二度数えられることはない）
よって、各 \(i=1,2,\dots,N\) について要素数 \(i\) の \(\{1,\cdots,N\}\) の部分集合 \(T\) であって \(\sum_{x \in T} A_x=X\) を満たすものの総数を求めればよく、これは以下のような状態を持った動的計画法で求めることができます。
\(\mathrm{dp}[i][j][k]:=\) 要素数 \(k\) の \(\{1,\cdots,i\}\) の部分集合 \(T\) であって \(\sum_{x \in T} A_x=j\) を満たすものの総数
時間計算量は \(\Theta(N^2X)(=\Theta(N^3A_{\max}))\) です。
投稿日時:
最終更新: