来点位运算优化，目前也是拿下了洛谷最优解，比第二名快一倍：
#include<bits/stdc++.h>
#define int long long
#define btp(x) __builtin_popcount(x)
#define lowbit(x) ((x)&(-x))
using namespace std;
namespace FastIO
{
template<typename T=int> inline T read()
{
T s=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) s=(s*10)+(c^48),c=getchar();
return s*w;
}
template<typename T> inline void read(T &s)
{
s=0; int w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) s=(s*10)+(c^48),c=getchar();
s=s*w;
}
template<typename T,typename... Args> inline void read(T &x,Args &...args)
{
read(x),read(args...);
}
template<typename T> inline void write(T x,char ch)
{
if(x<0) x=-x,putchar('-');
static char stk[25]; int top=0;
do {stk[top++]=x%10+'0',x/=10;} while(x);
while(top) putchar(stk[--top]);
putchar(ch);
return;
}
}
using namespace FastIO;
bool Mbe;
namespace LgxTpre
{
static const int MAX=21;
static const int Mod=1e9+7;
int n,f[1<<MAX],g[MAX];
template<typename T> inline void Madd(T &a,T b) {a=a+b>Mod?a+b-Mod:a+b;}
inline void dry()
{
read(n),f[0]=1;
for(int i=0;i<n;++i) for(int j=0;j<n;++j) g[i]|=read()<<j;
for(int S=1,i=btp(S);S<(1<<n);++S,i=btp(S)) for(int T=S&g[i-1];T;T&=T-1) Madd(f[S],f[S&(~(lowbit(T)))]);
write(f[(1<<n)-1],'\n');
}
}
bool Med;
signed main()
{
fprintf(stderr,"%.3lf MB\n",abs(&Med-&Mbe)/1048576.0);
int Tbe=clock();
LgxTpre::dry();
int Ted=clock();
cerr<<1e3*(Ted-Tbe)/CLOCKS_PER_SEC<<" ms\n";
return (0-0);
}
代码非常好理解。首先是存关系，直接压成二进制表示有无边就好了，记关系集合为 \(g\)。记当前集合为 \(S\)，找二进制下有几个 \(1\)，可以直接用 __builtin_popcount，记为 \(i\)。钦定当前是第 \(i\) 个左部点向右匹配，直接将 \(g_i\) 和 \(S\) 取交就是可匹配的右部点集合，记为 \(T\)。用类似枚举子集的操作遍历 \(T\) 二进制下的每个 \(1\)，可以每次去掉 \(T\) 二进制下最后一个 \(1\)。要从 \(S\) 中依次枚举去掉哪一个 \(1\)，相当于把 \(T\) 的最后一个 \(1\) 去掉后全部取反再和 \(S\) 取交，快速找 \(1\) 可以用 lowbit 加速。
当然还有进一步优化的空间：少取几次模，把 #define int long long 去了等。