## 2013年2月10日日曜日

### HackerCup 2013 Round2 Permutations

N個の整数と、それらの整数に関するN-1個の二項関係が与えられる。すべての二項関係を満たすN個の整数の順列のパターン数（MOD 1000000007）を求めよ。

```using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)

const long long MOD = 1000000007;
vector<pair<int, int> > edge[1024];
long long comb[1024][1024];

vector<long long>dfs(int v, int p = -1) {
vector<long long> x(1, 1);

REP (k, edge[v].size()) {
int u = edge[v][k].first;
if (u == p)
continue;
vector<long long> y = dfs(u, v);
if (edge[v][k].second) {   // v < w
for (int i = (int)y.size()-1; i > 0; i--)
y[i-1] = (y[i] + y[i-1]) % MOD;
y.push_back(0);
}
else {                     // v > w
for (int i = 1; i < (int)y.size(); i++)
y[i] = (y[i] + y[i-1]) % MOD;
y.insert(y.begin(), 0);
}

vector<long long>tmp = vector<long long>(x.size() + y.size() - 1);
REP (i, x.size()) REP (j, y.size()) {
long long p = x[i] * y[j] % MOD;
long long q = comb[i+j][j] * comb[x.size()-1-i+y.size()-1-j][y.size()-1-j] % MOD;
tmp[i+j] = (tmp[i+j] + p * q % MOD) % MOD;
}
x = tmp;
}
return x;
}

long long solve() {
REP (i, 1024)
edge[i].clear();

int n, a, b;
char c;
cin >> n;
REP (i, n-1) {
cin >> a >> c >> b;
edge[a].push_back(make_pair(b, c=='<'));
edge[b].push_back(make_pair(a, c=='>'));
}

vector<long long> res = dfs(0);

long long ret = 0;
REP (i, n)
ret = (ret + res[i]) % MOD;
return ret;
}

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

int main() {
int T;
cin >> T;

init();
REP (i, T) {
cerr << "solving #" << (i+1) << "...." << endl;
long long ret = solve();
cout << "Case #" << (i+1) << ": " << ret << endl;
}

return 0;
}
```