题解：【AT Educational DP Contest-O】 Matching

题目链接

来点位运算优化，目前也是拿下了洛谷最优解，比第二名快一倍：

#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 去了等。