ARC087 F : Squirrel Migration(800)
作成日：2017.12.19
最終更新日：2017.12.19
問題概要
$N$頂点からなる木がある。
頂点には$1$から$N$まで番号が振られており、$i$番目の辺は$x_i$と$y_i$を結んでいる。
また頂点$v,w$間の距離$d(v,w)$を、$v,w$間のパスに含まれる辺の本数とする。
$\{1,2,..,N\}$の順列$p$を$\sum{d(i,p_i)}$が最大となるように選ぶ。
このような$p$の選び方を$10^9 + 7$で割った余りを求めよ。
制約
$1 \leq N \leq 5000$
$1 \leq x_i , y_i \leq N$
考え方
まず、どのような順列が条件を満たすか考える。
それぞれの辺が$i,p_i$間のパスとして使われる最大の回数は、その辺を切った時にできる2つの連結成分のうち要素数が大きくない方$T$の要素数の2倍である。
この回数は$T$にあるすべての要素$i$について$p_i$が$T$に含まれないようにすれば達成できる。
これはすべての辺について同時に達成することが可能である。
条件を満たす順列の数を求めるために、その頂点につながるどの辺を切っても自身は$T$の要素数以上の要素を持つ連結成分に含まれる木の重心を考える。
重心が2つある時は要素数が$N/2$である連結成分を2つ結ぶ辺が存在する。
この辺について先に述べた条件を満たすと自動的に他の辺についてもその条件を満たすようになる。
よってこの時の答えは$((N/2)!)^2$である。
以下では重心が$g$の1つである時を考える。
$g$につながる辺すべてについて先に述べた条件を満たせば、他の辺についてもその条件を満たすようになる。
与えられた木から$g$とそれにつながる辺を取り除いた森を考え、森の各連結成分を$T_i$とする。
すると順列$p$は、「$x$は$T_i$に含まれるが$p_x$は$T_i$に含まれない」という条件$Q$をすべての$x$について満たすようなものであれば良いといえる。
このような順列$p$を数えるのは難しいが、ある$x$が条件$Q$を満たさないような順列を数えると求められることから包除原理を用いると可能であることが分かる。
集合$S$に含まれる要素が条件$Q$を満たさないような順列の数を考える。
$S$の要素がすべて同じ連結成分$T_i$に含まれているとすると、これは$(N-|S|)!$$\times \frac{|T_i|!}{(|T_i|-|S|)!}$である。
そうでない時も同様に考えると、$S_i = S \cap T_i$とすると$(N-|S|)!$$\times \prod \frac{|T_i|!}{(|T_i|-|S_i|)!}$である。
よって答えは、$g$以外のすべての頂点の集合の部分集合$S$それぞれにおいて上記の値に$(-1)^{|S|}$を乗じたものの総和である。
これを愚直に求めると$O(2^N)$となり間に合わないので工夫する。
答えの式を見ると、$|S|$のみに依存する部分と$|S_i|$及び$|T_i|$のみに依存する部分に分けられることが分かる。
$|S|$$= \sum |S_i|$であることから、$\sum |S_i|$を状態として持つdpを$T_i$ごとに見ていくことで更新すれば良さそうである。
$|S_i|$が同じものは$_{|T_i|}C_{|S_i|}$個存在することを考えると、更新は$O(N)$で行うことができる。
このdpの計算量は$O(N^2)$であるから十分高速である。
ソースコード
マクロ等はこちら
const int MC = 5010;
const LL mod = 1e9 + 7;
int N;
vector<int> V[MC];
int c[MC],parent[MC];
int g = -1;
LL fct[MC+1];
LL invfct[MC+1];
LL dp[2][MC];
void build(){
fct[0] = fct[1] = 1;
repp(i,2,MC+1){
fct[i] = fct[i-1] * i % mod;
}
LL x = fct[MC];
invfct[MC] = 1;
for(int i = mod - 2 ; i > 0 ; i >>= 1){
if(i % 2 == 1) (invfct[MC] *= x) %= mod;
(x *= x) %= mod;
}
repm(i,MC,0){
invfct[i-1] = invfct[i] * i % mod;
}
}
LL func(int x , int y){
return fct[x] * fct[x] % mod * invfct[y] % mod * invfct[x-y] % mod * invfct[x-y] % mod;
}
void dfs(int p , int q){
bool b = 1;
c[q] = 1;
parent[q] = p;
for(auto u : V[q]){
if(u == p) continue;
dfs(q,u);
if(c[u]*2 >= N) b = 0;
c[q] += c[u];
}
if(b && c[q] * 2 > N) g = q;
}
int main(){
build();
cin >> N;
repp(i,1,N){
int x,y;
cin >> x >> y;
V[x].PB(y);
V[y].PB(x);
}
dfs(-1,1);
if(g<0) return cout << fct[N/2] * fct[N/2] % mod << endl , 0;
repp(i,0,N-c[g]+1) dp[0][i] = func(N-c[g],i);
int z = 0;
for(auto u : V[g]){
if(u == parent[g]) continue;
fill(dp[!z],dp[!z]+MC,0);
repp(i,0,N+1){
repp(j,0,c[u]+1){
if(i+j>=N) break;
(dp[!z][i+j] += dp[z][i] * func(c[u],j)) %= mod;
}
}
z = !z;
}
LL ans = 0;
int sgn = 1;
repp(i,0,N){
(ans += sgn * dp[z][i] * fct[N-i]) %= mod;
sgn *= -1;
}
if(ans<0) ans += mod;
cout << ans << endl;
return 0;
}解法まとめ
まず木の重心を求める。(31-42行)
重心が2つある時、答えは$((N/2)!)^2$である。(54行)
重心が1つである時は、条件$Q$を満たさない要素の数を状態として持ち$T_i$ごとに値を更新していくdpを行う。(55-67行)
最終的な答えは$\sum (-1)^i$$\times dp_i$$\times (N-i)!$である。(68-75行)