f[i][j]: i表示整个图走没走过的状态 j表示当前到了第j个点 存的值就是在这种情形下 可以走到的地方的状态
dp[i][j]:i表示整个图走没走过的状态 j表示当前在j点 访问剩余能去到的点的方案数
因此只需要跑一遍DFS就好了
#include<bits/stdc++.h> #define int long long #define mod 998244353 #define N 19 #define M 400 using namespace std; int n,m,first[N],tot; int f[1<<N][N],dp[1<<N][N]; struct node { int to,next; }edge[2*M]; inline void addedge(int x,int y) { tot++; edge[tot].to=y; edge[tot].next=first[x]; first[x]=tot; } int dfs1(int sta,int now) { if(f[sta][now]) return f[sta][now]; f[sta][now]=sta; //sta一定是f[sta][now]的子集 for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(!(sta&(1<<vis))) //这个点没有走过 { f[sta][now]|=dfs1(sta|(1<<vis),vis); //要"并"进去 } } return f[sta][now]; } int dfs2(int sta,int now) { if(f[sta][now]==sta) return 1; if(dp[sta][now]!=-1) return dp[sta][now]; dp[sta][now]=0; for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(sta&(1<<vis)) continue; int x=dfs2(sta|(1<<vis),vis); int y=dfs2(f[sta|(1<<vis)][vis],now); dp[sta][now]+=x*y%mod; } return dp[sta][now]%=mod; } main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>m; for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; x--; y--; addedge(x,y); addedge(y,x); } for(int i=0;i<(1<<n);i++) { for(int j=0;j<n;j++) { if(i&(1<<j)) { f[i][j]=dfs1(i,j); } } } memset(dp,-1,sizeof(dp)); int ans=0; for(int i=0;i<n;i++) { ans=(ans+dfs2(1<<i,i))%mod; } cout<<ans%mod; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9805795.html
相关资源：各显卡算力对照表！