有一个有向图。这张图有n个点和m条有向边。 他很好奇不相交的环（简单环）来覆盖所有点的方案数（数字可能很大请模998,244,353)。 Input 第一行有n和m。(1<=n<=20,1<=m<=n*(n-1)) 后面m行描述着m条边。 输入保证没有重边自环。 Output 输出方案数。 Sample Input 3 3 1 2 2 3 3 1 Sample Output 1
把每一个点拆成前驱和后继，连边。 然后发现如果满足题意，则形成一个二分图的完全匹配。 用状压dp，dp[i][j]：x部有i个点匹配，j用二进制表示y部匹配的点。 虽然实际操作不用拆点emmm… 详见代码。
#include<cstdio> #include<vector> #include<cstring> #define maxn 20 #define mod 998244353 using namespace std; int n,m,f[maxn+5][(1<<maxn)+5]; vector<int> G[maxn+5]; int dp(int i,int j) { if(i<0||j<0) return j==0; if(f[i][j]>=0) return f[i][j]; f[i][j]=0; for(int k=0;k<G[i].size();k++) { int v=G[i][k]; if((1<<v)&j) { f[i][j]+=dp(i-1,j-(1<<v)); f[i][j]%=mod; } } return f[i][j]; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); G[u-1].push_back(v-1); } memset(f,-1,sizeof(f)); printf("%d\n",dp(n-1,(1<<n)-1)); }