1742번: 레이싱결과

https://www.acmicpc.net/problem/1742

#include<cstdio>
#include<map>
#include<vector>
#define mod 1000003
using namespace std;
map<int, int> dp;
vector<int> adj[31], radj[31];
int n, m, r = 1, vis[31], c[31][31], cnt, ind[31], p, s;
void f(int h) {
    if (vis[h]) return;
    vis[h] = p;
    cnt++;
    for (int it : adj[h]) f(it);
    for (int it : radj[h]) f(it);
}
int g(int h) {
    if (dp.find(h) != dp.end()) return dp[h];
    if (!h) {
        for (int i = 1; i <= n; i++) if (vis[i] == p&&ind[i]) return 0;
        return 1;
    }
    int &ret = dp[h];
    for (int i = 1; i <= n; i++) if (h & 1 << i) {
        int t = h ^ 1 << i;
        for (int it : adj[i]) if (!--ind[it]) t ^= 1 << it;
        ret = (ret + g(t)) % mod;
        for (int it : adj[i]) ind[it]++;
    }
    return ret;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i <= n; i++) {
        c[i][0] = 1;
        for (int j = 1; j <= i; j++) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
    }
    for (int x, y; m--;) {
        scanf("%d%d", &x, &y);
        adj[x].push_back(y);
        radj[y].push_back(x);
        ind[y]++;
    }
    for (p = 1, s = n; p <= n; p++) if (!vis[p]) {
        cnt = 0;
        f(p);
        int t = 0;
        for (int i = p; i <= n; i++) if (vis[i] == p && !ind[i]) t |= 1 << i;
        r = 1LL * r * g(t) % mod*c[s][cnt] % mod;
        s -= cnt;
    }
    printf("%d", r);
    return 0;
}