Submission #48005809

---

Source Code Expand

#include<bits/stdc++.h>
#define ll long long
#define db double
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define FR first
#define SE second
using namespace std;
inline int read() {
  int x = 0; bool op = false;
  char c = getchar();
  while(!isdigit(c))op |= (c == '-'), c = getchar();
  while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return op ? -x : x;
}
const int P = 1e9 + 7;
void add(int &a, int b) {a += b; a >= P ? a -= P : 0;}
void sub(int &a, int b) {a -= b; a < 0 ? a += P : 0;}
int n, m;
int g[20], f[1 << 15];
int main() {
  n = read(); m = read();
  for(int i = 1; i <= m; i++) {
    int u = read() - 1, v = read() - 1;
    g[u] |= (1 << v);
  }
  f[0] = 1;
  for(int i = 0; i < (1 << n); i++) {
    int t = ((1 << n) - 1) ^ i;
    for(int s = t; s; s = (s - 1) & t) {
      if((s & 1) && (s >> 1 & 1))continue;
      int coef = 1;
      for(int j = 0; j < n; j++) {
        if(s >> j & 1)continue;
        int v = __builtin_popcount(g[j] & s);
        coef = 1ll * coef * ((1 << v) - (~i >> j & 1)) % P;
      }
      add(f[i | s], 1ll * coef * f[i] % P);
    }
  }
  printf("%d\n", f[(1 << n) - 1]); 
  return 0;
}

Submission Info

Judge Result