我们考虑先枚举填 $2$ 的位置。那么剩下的位置之可能填 $0$ 或 $1$。同时我们用约束条件判断每一个位置取 $0$，取 $1$，都可以或不可能。

如果存在不可能，那么这些位置填 $2$ 的方案数不计入答案。接着我们取出都可以取的点的集合 $S$，考虑这一部分的答案 $f(S)$。

我们钦定其中一个点取 $0$ 还是 $1$,然后考虑限制，接着就变成了子问题。

代码实现上，值的注意的是 $A$ 确定了 $B$ 之后，$B$ 还可以确定 $C$。

以及一开始枚举的填 $2$ 的集合之间的约束也要考虑。

时间复杂度 $O(2^n \cdot n^2)$，小常数。

代码比较混乱。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
// #pragma GCC optimize(2,3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int maxn=22;
const int maxm=1<<maxn;
int n,m;
int lg[maxm];
vector<int> ban[3][3][maxn];
bool ban2[maxn+5][maxn+5];
bool flg[maxn][2];
int f[maxm];
ll ans;
inline int Lowbit(int x){return x&(-x);}
inline void Delete(int p,int c){
    for(int j:ban[c][0][p]) flg[j][0]=1;
    for(int j:ban[c][1][p]) flg[j][1]=1;
}
inline int Find(int s){
    for(;s;s^=Lowbit(s)){
        int i=lg[Lowbit(s)];
        if(flg[i][0]==1&&flg[i][1]==0) return i<<1|1;
        if(flg[i][0]==0&&flg[i][1]==1) return i<<1;
        if(flg[i][0]==1&&flg[i][1]==1) return -1;
    }
    return -2;
}
inline int Calc(int s){
    int x;
    while(true){
        x=Find(s);
        if(x==-2) return s;
        if(x==-1) return -1;
        s^=1<<(x>>1);
        Delete(x>>1,x&1);
    }
}
signed main(){
    // freopen("paint.in","r",stdin);
    int a,b,x,y;
    scanf("%d%d",&n,&m);
    for(int i=0,t=1;i<n;i++,t<<=1) lg[t]=i;
    while(m--){
        scanf("%d%d%d%d",&a,&x,&b,&y);
        a--,b--;
        ban[x][y][a].emplace_back(b);
        ban[y][x][b].emplace_back(a);
        if(x==2&&y==2) ban2[a][b]=ban2[b][a]=1;
    }
    int t;
    f[0]=1;
    for(int i=1;i<(1<<n);i++){
        memset(flg,0,sizeof(flg));
        Delete(lg[Lowbit(i)],0);
        t=Calc(i^Lowbit(i));
        if(~t) f[i]+=f[t];
        memset(flg,0,sizeof(flg));
        Delete(lg[Lowbit(i)],1);
        t=Calc(i^Lowbit(i));
        if(~t) f[i]+=f[t];
        // cerr<<f[i]<<endl;
    }
    for(int i=0;i<(1<<n);i++){
        bool chk=0;
        for(int j=i;j;j^=Lowbit(j))
            for(int k=j^Lowbit(j);k;k^=Lowbit(k))
                chk|=ban2[lg[Lowbit(j)]][lg[Lowbit(k)]];
        if(chk) continue;
        memset(flg,0,sizeof(flg));
        for(int j=i;j;j^=Lowbit(j))
            Delete(lg[Lowbit(j)],2);
        t=Calc(((1<<n)-1)^i);
        if(~t) ans+=f[t];
    }
    printf("%lld",ans);
    return 0;
}