Submission #1361786

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const int md = 1000000007;

inline void add(int &a, int b) {
  a += b;
  if (a >= md) {
    a -= md;
  }
}

inline int mul(int a, int b) {
  return (long long) a * b % md;
}

const int N = 1234567;

int who[N];
int mask[N];
int kb[N];
int g[N];
int deg[N];
int ans;

void dfs(int v, int ways) {
  if (v == 1) {
    int rm0 = deg[0];
    int rm1 = deg[1];
    int z = 0;
    while (true) {
      int cur0 = kb[mask[0] & who[z]];
      int cur1 = kb[mask[1] & who[z]];
      add(ans, mul(ways, 1 << (rm0 - cur0 + rm1 - cur1)));
      if (cur0 == 0 || cur1 == 0) {
        break;
      }
      rm0 -= cur0;
      rm1 -= cur1;
      ways = mul(ways, (1 << cur0) - 1);
      ways = mul(ways, (1 << cur1) - 1);
      z++;
    }
    return;
  }
  g[v] = 0;
  int rm = deg[v];
  while (true) {
    int cur = kb[mask[v] & who[g[v]]];
    who[g[v]] ^= (1 << v);
    dfs(v - 1, mul(ways, 1 << (rm - cur)));
    who[g[v]] ^= (1 << v);
    if (cur == 0) {
      break;
    }
    rm -= cur;
    ways = mul(ways, (1 << cur) - 1);
    g[v]++;
  }
}

int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    x--; y--;
    mask[x] |= (1 << y);
  }
  if (mask[0] & 2) {
    mask[0] ^= 2;
  }
  kb[0] = 0;
  for (int i = 1; i < (1 << n); i++) {
    kb[i] = kb[i & (i - 1)] + 1;
  }
  for (int i = 0; i < n; i++) {
    deg[i] = kb[mask[i]];
  }
  for (int z = 0; z <= n; z++) {
    who[z] = 0;
  }
  ans = 0;
  dfs(n - 1, 1);
  int total = 1;
  for (int i = 0; i < m; i++) {
    add(total, total);
  }
  int res = total;
  add(res, md - ans);
  printf("%d\n", res);
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:65:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &m);
                         ^
./Main.cpp:68:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &x, &y);
                           ^

Judge Result