Submission #1363159

---

Source Code Expand

#pragma GCC optimize "-Ofast"
#include <bits/stdc++.h>

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long long llong;
typedef long double ld;

using namespace std;

template <typename T> void dprint(T begin, T end) {
    for (auto i = begin; i != end; i++) {
        cerr << (*i) << " ";
    }
    cerr << "\n";
}
const ll MOD = 1e9 + 7;

int n, m;
ll ans;

vector<int> eds[16];
int a[16];

int pp[16];
int pw[16];

void run(int x, ll now) {
    if (x == 1) {
        int cnt1[16];
        int cnt2[16];
        memset(cnt1, 0, sizeof(cnt1));
        for (int u: eds[0])
            ++cnt1[a[u]];
        memset(cnt2, 0, sizeof(cnt2));
        for (int u: eds[1])
            ++cnt2[a[u]];
        int g = eds[0].size() + eds[1].size();
        ll cur = now;
        for (int i = 0; cur != 0; ++i) {
            g -= cnt1[i] + cnt2[i];
            ans = (ans + cur * (1 << g)) % MOD;
            cur = (cur * ((1 << cnt1[i]) - 1)) % MOD;
            cur = (cur * ((1 << cnt2[i]) - 1)) % MOD;
        }
        return;
    }
    int cnt[16];
    memset(cnt, 0, sizeof(cnt));
    for (int u: eds[x])
        ++cnt[a[u]];
    int g = eds[x].size();
    ll cur = now;
    for (int i = 0; cur != 0; ++i) {
        g -= cnt[i];
        a[x] = i;
        run(x - 1, (cur * pw[g]) % MOD);
        cur = (cur * pp[cnt[i]]) % MOD;
    }
}

int main() {
    for (int i = 0; i < 16; ++i)
        pw[i] = (1 << i);
    for (int i = 0; i < 16; ++i)
        pp[i] = pw[i] - 1;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        if (a != 0 || b != 1)
            eds[a].push_back(b);
    }
    run(n - 1, 1);
    ll ans2 = 1;
    for (int i = 0; i < m; ++i)
        ans2 = (ans2 * 2) % MOD;
    ans2 -= ans;
    if (ans2 < 0)
        ans2 += MOD;
    cout << ans2 << "\n";
    return 0;
}

Submission Info

Judge Result