Submission #1363869

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <string>
#include <cstring>
#include <complex>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define mp make_pair

const int MOD = (int)1e9 + 7;
int add(int x, int y)
{
    x += y;
    if (x >= MOD) return x - MOD;
    return x;
}
int sub(int x, int y)
{
    x -= y;
    if (x < 0) return x + MOD;
    return x;
}
int mult(int x, int y)
{
    return ((ll)x * y) % MOD;
}
int bin_pow(int x, int p)
{
    if (p == 0) return 1;
    if (p & 1) return mult(x, bin_pow(x, p - 1));
    return bin_pow(mult(x, x), p / 2);
}
int rev(int x)
{
    return bin_pow(x, MOD - 2);
}

const int S = 6000011;
struct HashTable
{
    pii a[S];

    HashTable() {
        for (int i = 0; i < S; i++)
            a[i] = mp(-1, 0);
    }

    int get(int x) {
        int h = (x + (x / S) * 45 + (x % S) * 123) % S;
        while(a[h].first != x && a[h].first != -1) {
            h++;
            if (h == S) h = 0;
        }
        if (a[h].first == x) return a[h].second;
        return 0;
    }

    void set(int x, int y) {
        int h = (x + (x / S) * 45 + (x % S) * 123) % S;
        while(a[h].first != x && a[h].first != -1) {
            h++;
            if (h == S) h = 0;
        }
        a[h] = mp(x, y);
    }
};

const int N = 15;
const int M = N * N + 2;
bool G[N][N];
int n;
int p2[M], rp2[M];
HashTable dp[2];

int getId(vector<int> &p) {
    int res = 0;
    for (int i = (int)p.size() - 1; i >= 0; i--)
        res = res * (i + 1) + p[i];
    return res;
}
vector<int> getVec(int n, int id) {
    vector<int> p;
    p.resize(n);
    for (int i = 0; i < n; i++) {
        p[i] = id % (i + 1);
        id /= i + 1;
    }
    return p;
}

int q1[N], q2[N];
int getAns(vector<int> &p)
{
    for (int i = 0; i < n; i++)
        q1[i] = q2[i] = 0;
    int curP = 1;
    for (int i = 0; i < (int)p.size(); i++) {
        if (G[n - 1][i]) {
            curP = add(curP, curP);
            q1[p[i]]++;
        }
        if (G[n - 2][i]) {
            curP = add(curP, curP);
            q2[p[i]]++;
        }
    }
    int ans = 0;
    for (int j = 0; curP != 0; j++) {
        curP = mult(curP, rp2[q1[j] + q2[j]]);
        ans = add(ans, curP);
        curP = mult(curP, (p2[q1[j]] - 1) * (p2[q2[j]] - 1));
    }
    return ans;
}

int solve()
{
    if (n == 3) {
        int ans = 1;
        if (G[2][0] && G[1][0]) ans++;
            return ans;
    }
    
    vector<int> p;
    p.push_back(0);
    dp[0].set(getId(p), 1);

    vector<int> q(n);
    
    for (int i = 1; i < n - 3; i++) {
        
        dp[1] = HashTable();

        for (int h = 0; h < S; h++)
        {
            if (dp[0].a[h].first == -1) continue;
            p = getVec(i, dp[0].a[h].first);
            for (int j = 0; j < i + 2; j++)
                q[j] = 0;
            int curP = dp[0].a[h].second;
            for (int j = 0; j < i; j++)
                if (G[i][j]) {
                    q[p[j]]++;
                    curP = add(curP, curP);
                }
            for (int j = 0; curP != 0; j++) {
                p.push_back(j);
                int id = getId(p);
                int val = dp[1].get(id);
                curP = mult(curP, rp2[q[j]]);
                val = add(val, curP);
                dp[1].set(id, val);
                curP = mult(curP, sub(p2[q[j]], 1));
                p.pop_back();
            }
        }

        dp[0] = dp[1];
    }

    int ans = 0;

    for (int h = 0; h < S; h++)
    {
        if (dp[0].a[h].first == -1) continue;
        p = getVec(n - 3, dp[0].a[h].first);
        for (int j = 0; j < n; j++)
            q[j] = 0;
        int curP = dp[0].a[h].second;
        for (int j = 0; j < n - 3; j++)
            if (G[n - 3][j]) {
                q[p[j]]++;
                curP = add(curP, curP);
            }
        for (int k = 0; k < n; k++)
            q1[k] = q2[k] = 0;

        int curP2 = 1;
        for (int i = 0; i < n - 2; i++) {
            if (G[n - 1][i]) curP2 = add(curP2, curP2);
            if (G[n - 2][i]) curP2 = add(curP2, curP2);
        }
        for (int i = 0; i < n - 3; i++) {
            if (G[n - 1][i]) {
                q1[p[i]]++;
            }
            if (G[n - 2][i]) {
                q2[p[i]]++;
            }
        }

        for (int j = 0; curP != 0; j++) {

            if (G[n - 1][n - 3]) {
                q1[j]++;
            }
            if (G[n - 2][n - 3]) {
                q2[j]++;
            }

            curP = mult(curP, rp2[q[j]]);
            int curP3 = mult(curP, curP2);

            for (int k = 0; curP3 != 0; k++) {
                curP3 = mult(curP3, rp2[q1[k] + q2[k]]);
                ans = add(ans, curP3);
                curP3 = mult(curP3, (p2[q1[k]] - 1) * (p2[q2[k]] - 1));
            }

            curP = mult(curP, sub(p2[q[j]], 1));

            if (G[n - 1][n - 3]) {
                q1[j]--;
            }
            if (G[n - 2][n - 3]) {
                q2[j]--;
            }
        }
    }

    return ans;
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    p2[0] = 1;
    rp2[0] = 1;
    for (int i = 1; i < M; i++) {
        p2[i] = add(p2[i - 1], p2[i - 1]);
        int x = rp2[i - 1];
        if (x & 1) x += MOD;
        rp2[i] = x / 2;
    }

/*
    n = 15;
    int m = n * (n - 1) / 2;
    for (int i = 1; i < n; i++)
        for (int j = 0; j < i; j++)
            G[i][j] = 1;
*/

    int m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int v, u;
        scanf("%d%d", &v, &u);
        v = n - v;
        u = n - u;
        G[v][u] = 1;
    }


    if (n == 2) {
        if (m == 0)
            printf("0\n");
        else
            printf("1\n");
        return 0;
    }

    int ans = solve();
    printf("%d\n", sub(p2[m], ans));

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:256:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
                          ^
./Main.cpp:259:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &v, &u);
                              ^

Judge Result