fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. typedef long long ll;
  4. #define pb push_back
  5. using namespace std;
  6.  
  7. int n, m;
  8. const int mod = 1e9 + 7;
  9. // Faktorial = 20! Tinggi O(N!)
  10. const int N = 20;
  11. ll dp[N][1 << N]; // Change type to ll to match rec return type
  12. vector<int> adj[N];
  13.  
  14. ll rec(int cur, int mask) {
  15.     if (cur == (n - 1) && mask == ((1 << n) - 1)) return 1;
  16.     if (cur == (n - 1)) return 0;
  17.     if (dp[cur][mask] != -1) return dp[cur][mask];
  18.     int ans = 0;
  19.     for (auto neighbour : adj[cur]) {
  20.         // neighbour = 1
  21.         // Cek jika neighbour sudah divisit atau belom
  22.         if ((1 << neighbour) & mask) continue;
  23.         (ans += rec(neighbour, mask | (1 << neighbour))) %= mod;
  24.     }
  25.     return dp[cur][mask] = ans;
  26. }
  27.  
  28. int main() {
  29.     cin.tie(0) -> sync_with_stdio(false), cout.tie(0);
  30.     // bikin jadi 0 indexing
  31.     cin >> n >> m;
  32.     memset(dp, -1, sizeof dp);
  33.     while (m--) {
  34.         int u, v;
  35.         cin >> u >> v;
  36.         u--, v--;
  37.         adj[u].pb(v);
  38.     }
  39.     cout << rec(0, 1) << "\n";
  40.     return 0;
  41. }
Success #stdin #stdout 0.03s 167408KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/0DgPWn
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!