Submission #1771426

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

const int mod = 1000*1000*1000+7;

int N, M;
vector<vector<int> > adj;
vector<vector<int> > Sub;
vector<vector<int> > prec;
vector<int> po;

vector<int> cc;
int dp(int mask) {
    int &ret = cc[mask];
    if(ret != -1) return ret;

    ret = 1;
    for(int i = 0; i < Sub[mask].size(); i++) {
        int nmask = Sub[mask][i];
        if(nmask == 0 || nmask == mask) continue;
        if((nmask & 3) != 0 && (nmask & 3) != 3) continue;

        int tmp = 1;
        for(int j = 0; j < N; j++) {
            if((nmask & (1<<j))) tmp = 1LL * tmp * (po[ prec[j][ mask ^ nmask ] ] - 1) % mod;
            if(((mask ^ nmask) & (1<<j))) tmp = 1LL * tmp * po[ prec[j][nmask] ] % mod;
        }
        tmp = 1LL * tmp * dp(nmask) % mod;
        ret += tmp;
        ret %= mod;
    }

    return ret;
}

int main() {
    po.resize(1000);
    po[0] = 1;
    for(int i = 1; i < 1000; i++) {
        po[i] = po[i - 1] * 2 % mod;
    }

    scanf("%d %d", &N, &M);

    adj.resize(N);

    for(int i = 0; i < M; i++) {
        int x, y; scanf("%d %d", &x, &y);
        x--; y--;

        adj[x].push_back(y);
    }

    Sub.resize(1 << N);
    for(int i = 0; i < (1 << N); i++) {
        if(i == 0) {
            Sub[i].push_back(0);
            continue;
        }
        for(int j = 0; j < Sub[ i - (i&-i) ].size(); j++) {
            Sub[i].push_back(Sub[ i - (i&-i) ][j]);
            Sub[i].push_back(Sub[ i - (i&-i) ][j] + (i&-i));
        }
    }

    prec = vector<vector<int> >(N, vector<int>(1 << N, 0));
    for(int u = 0; u < N; u++) {
        for(int mask = 0; mask < (1 << N); mask++) {
            int cnt = 0;
            for(int i = 0; i < adj[u].size(); i++) {
                int v = adj[u][i];
                if(mask & (1<<v)) cnt++;
            }
            prec[u][mask] = cnt;
        }
    }

    cc = vector<int>(1 << N, -1);
    cout << (po[M] - dp((1 << N) - 1) + mod) % mod;
}

Submission Info

Compile Error

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

Judge Result