Facebook Hacker Cup Round 2

C.cpp

#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <numeric>

#include <sys/types.h>
#include <sys/wait.h>

using namespace std;

#define MOD 1000000007

int N;
vector<pair<int, bool> > E[1010];

int NCR[1010][1010];

vector<int> solve(int u, int p) {
  vector<int> R(1, 1);
  for(int i = 0; i < E[u].size(); i++) {
    if(p == E[u][i].first) continue;

    vector<int> C = solve(E[u][i].first, u);
    if(E[u][i].second) {
      reverse(R.begin(), R.end());
      reverse(C.begin(), C.end());
    }

    int sz = R.size() + C.size();
    vector<int> A(sz, 0);
    vector<int> PC = C;
    for(int j = 1; j < C.size(); j++) {
      PC[j] = (PC[j] + PC[j - 1]) % MOD;
    }
    for(int a = 1; a < sz; a++) {
      for(int j = 1; j <= a && j <= C.size(); j++) {
        if(a - j >= R.size()) continue;

        int v = (1ll * R[a - j] * PC[j - 1]) % MOD;
        v = (1ll * NCR[a][j] * v) % MOD;
        v = (1ll * NCR[sz - a - 1][C.size() - j] * v) % MOD;
        A[a] = (A[a] + v) % MOD;
      }
    }
    R.swap(A);

    if(E[u][i].second) {
      reverse(R.begin(), R.end());
    }
  }
  return R;
}

int main() {
  for(int i = NCR[0][0] = 1; i < 1010; i++) {
    for(int j = NCR[i][0] = NCR[i][i] = 1; j < i; j++) {
      NCR[i][j] = (NCR[i - 1][j - 1] + NCR[i - 1][j]) % MOD;
    }
  }

  int T; scanf("%d", &T);
  for(int t = 1; t <= T; t++) {
    printf("Case #%d: ", t);

    scanf("%d", &N);
    for(int i = 0; i < N; i++) E[i].clear();

    for(int i = 1; i < N; i++) {
      int u, v;
      char cmp[4];
      scanf("%d %2s %d", &u, cmp, &v);
      if(cmp[0] == '>') swap(u, v);

      E[u].push_back(make_pair(v, true));
      E[v].push_back(make_pair(u, false));
    }

    int res = 0;
    vector<int> V = solve(0, -1);
    for(int i = 0; i < V.size(); i++) {
      res = (res + V[i]) % MOD;
    }
    printf("%d\n", res);
  }
  return 0;
}