Submission #2412099

---

Source Code Expand

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int N, M;
vector <int> G[20];
bool Matrix[20][20];
int DP[15000005];
int Conf[20];
const int MOD = 1000000007;
int Cnt[(1 << 15) + 5];
void precalcCnt()
{
    int lim = (1 << N);
    for(int i = 1; i < lim; i++)
        for(int j = 0; j < N; j++)
            if((i & (1 << j)) != 0)
            {
                Cnt[i] = 1 + Cnt[(i ^ (1 << j))];
                break;
            }
}
void Read()
{
    cin >> N >> M;
    for(int i = 1; i <= M; i++)
    {
        int x, y;
        cin >> x >> y;
        --x;--y;
        G[x].push_back(y);
        //G[y].push_back(x);
        Conf[x] |= (1 << y);
        Matrix[x][y] = 1;
    }
    memset(DP, -1, sizeof(DP));
}
inline void Add(int& x, int y)
{
    x += y;
    if(x >= MOD)
        x -= MOD;
}
int Solve(int conf)
{
    if(DP[conf] != -1)
        return DP[conf];
    vector <int> V;
    bool X[20]; int C[20];
    for(int i = 0; i < N; i++)
    {
        X[i] = 0;
        C[i] = 0;
        if((conf & (1 << i)) != 0)
            V.push_back(i), X[i] = 1;
    }
    if(X[0] != X[1])
        return 0;
    for(int i = 0; i < V.size(); i++)
    {
        for(int j = 0; j < V.size(); j++)
            if(Matrix[V[i]][V[j]] == 1)
            {
                C[V[i]] |= (1 << V[j]);
            }
    }
    int sz = V.size();
    int ans = 1;
    for(int c = 1; c < (1 << sz) - 1; c++)
    {
        int mask1 = 0, mask2 = 0;
        int nb = 1;
        for(int j = 0; j < sz; j++)
        {
            if((c & (1 << j)) != 0)
            {
                mask1 = (mask1 ^ (1 << V[j]));
            }
            else
                mask2 = (mask2 ^ (1 << V[j]));
        }
        for(int j = 0; j < sz; j++)
        {
            if((c & (1 << j)) != 0)
            {
                int m = (Conf[V[j]] & mask2);
                int pw = (1 << Cnt[m]) - 1;
                nb = (1LL * nb * pw) % MOD;
            }
            else
            {
                int m = (Conf[V[j]] & mask1);
                int pw = (1 << Cnt[m]);
                nb = (1LL * nb * pw) % MOD;
            }
        }
        nb = (1LL * nb * Solve(mask1)) % MOD;
        Add(ans, nb);
    }
    DP[conf] = ans;
    return ans;
}
int main()
{
    Read();
    precalcCnt();
    int ans = Solve((1 << N) - 1);
    int p = 1;
    for(int i = 1; i <= M; i++)
        p = (1LL * p * 2) % MOD;
    ans = (p - ans) % MOD;
    if(ans < 0)
        ans += MOD;
    cout << ans << '\n';
    return 0;
}

Submission Info

Judge Result