#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; }
1742번: 레이싱결과
https://www.acmicpc.net/problem/1742
피드 구독하기:
댓글
(
Atom
)
댓글 없음 :
댓글 쓰기