记录编号	600220	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2015] 厕所里的OIer	最终得分	100
用户昵称	NahidaOI	是否通过	通过
代码语言	C++	运行时间	0.826 s
提交时间	2025-04-22 17:08:08	内存使用	19.33 MiB

#include<bits/stdc++.h>
#define int long long
#define Sangonomiya signed
#define Kokomi main()
#define Love return
#define Nahida 0
#define Forever ;
#define IOS cin.tie(nullptr)->sync_with_stdio(false)
#define cin std::cin
#define cout std::cout
const int N=1e6;
const int M=1<<20;
int b[M];
int dp[N],cur[N];
bool op[21][21];
std::vector<int> peo[21];
int n,m,now;
void init(){
    for(int i=0;i<M;i++) b[i]=__builtin_popcount(i);//这句话查的，作用是返回i在二进制下1的个数.
}
Sangonomiya Kokomi{
	freopen("scr_chess.in","r",stdin);
    freopen("scr_chess.out","w",stdout);
    cin>>n>>m;
    init();
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        op[--x][--y]=true;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(!op[i][j]) peo[i].push_back(j);
        }
    }
    dp[0]=1;
    for(int i=0;i<n;i++){
        memset(cur,0,sizeof(cur));
        for(int j=0;j<(1<<n);j++){
            if(dp[j]==0 || b[j]!=i) continue;
            for(int v:peo[i]){
                if(!(j&(1<<v))){
                    now=j|(1<<v);
                    cur[now]+=dp[j];
                }
            }
        }
        for(int j=0;j<(1<<n);j++){
            dp[j]=cur[j];
        }
    }
    cout<<dp[(1<<n)-1]<<'\n';
	Love Nahida Forever;
}