HackerCup 2013 Round2 Permutations

問題概要

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

解法

動的計画法を用いる。dfs(v, p)の解res[i]は節点vに対応する整数がi番目に現れる順列のパターン数を返す。

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;
}