5002 - The Queue

5002 - The Queue　Asia - Kuala Lumpur - 2010/2011
http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=5002

問題概要

上司と部下の関係が与えられる。
一人を除いて、ちょうど一人の上司をそれぞれの社員がもつ。
今、列を作る。
上司の前に並ばないようにする並び方は何通りあるか。

解法

分割統治。
木を作ってその部分木についてそれぞれ見ていく。
今空いている場所がnだとすると、部分木のノードの数、
場所を確保する。
今確保した場所の数を子に渡し、子は確保した部分を空いてる場所として処理する。
子以下の部分木のノード数の分は確保したのは使われたので、
他の子にまだ使われていなく、確保したノードの数を渡す。
再帰的に見ていく。
今の空いてる場所から部分木のノードの数を確保する組み合わせと、
子の各組み合わせを掛け合わせたものがその部分木の組み合わせの数である。

ソース

#include<iostream>
#include<vector>
#include<cstdio>

#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)

using namespace std;
typedef long long lli;
const lli  MOD = 1000000007;
const int N = 1001;

vector<int> Edge[N];
int haveNode[N];
bool root[N];
int n;
lli comb[N][N];

void makeComb(){
  rep(i, N){
    comb[0][i] = 0;
    comb[i][0] = 1;
  }
  REP(i, 1, N){
    REP(j, 1, N){
      comb[i][j] = comb[i-1][j] + comb[i-1][j-1];
      comb[i][j] %= MOD;
    }
  }
}

void init(){
  rep(i, N){
    haveNode[i] = -1;
    root[i] = true;
    Edge[i].clear();
  }
}

lli calcNode(int id){
  haveNode[id] = 1;
  FOR(it, Edge[id]){
    haveNode[id] += calcNode(*it);
  }
  return haveNode[id];
}

lli solve(int id, int remain){
  lli now = comb[remain][haveNode[id]];
  remain = haveNode[id]-1;
  FOR(it, Edge[id]){
    now *= solve(*it, remain);
    now %= MOD;
    remain -= haveNode[*it];
  }
  return now;
}

int main(){
  makeComb();
  int T;
  cin >> T;
  rep(tc, T){
    cin >> n;
    init();
    rep(i, n-1){
      int from, to;
      cin >> from >> to;
      from--;
      to--;
      Edge[from].push_back(to);
      root[to] = false;
    }
    rep(i, n){
      if(root[i])calcNode(i);
    }
    lli res = 1;
    int remain = n;
    rep(i, n){
      if(root[i])res *= solve(i, remain);
      res %= MOD;
    }
    printf("Case %d: %Ld\n", tc+1, res);
  }
  return 0;
}