简要题意
求一个图邻接矩阵的行列式，保证边双大小 (D) 小于等于40。
我们先考虑求一个带权方案数：(行列式 * (-1)^{点数})，其组合意义是分成若干个环，带 ((-1)^{环个数}) 的权
先缩点，记 (f[i][0/1]) 表示 (i) 子树内，向父亲连的桥边是否选中，带权的方案数。
向下连的桥边我们需要转化一下：考虑对每个点记录 (d_1, d_0) 表示是否选择桥边的带权方案数。
(d_1) 贡献到对角线上（连自环）， (d_0) 贡献到同一行其他位置即可。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
inline int add(int a,int b){a+=b;return a>=mod?a-mod:a;}
inline int sub(int a,int b){a-=b;return a<0?a+mod:a;}
inline int mul(int a,int b){return 1ll*a*b%mod;}
inline int qpow(int a,int b){int ret=1;for(;b;b>>=1,a=mul(a,a))if(b&1)ret=mul(ret,a);return ret;}
/* math */
const int N = 5e5+5;
int hed[N],from[N<<1],to[N<<1],nxt[N<<1],cnt=1,n,m;
inline void adde(int u,int v){
++cnt;from[cnt]=u,to[cnt]=v,nxt[cnt]=hed[u];hed[u]=cnt;
}
bool bridge[N<<1];
int ccnt;
vector<int> ecc[N];
int dfn[N],low[N],idx[N],rnk[N],num;
inline void tarjan(int x,int pre){
dfn[x]=low[x]=++num;
for(int i=hed[x];i;i=nxt[i]){
int v=to[i];if(v==pre)continue;
if(!dfn[v]){
tarjan(v,x);
low[x]=min(low[x],low[v]);
if(low[v]>dfn[x]){
bridge[i]=bridge[i^1]=1;
}
}else low[x]=min(low[x],dfn[v]);
}
}
bool vis[N];
void fin_ecc(int x,int id){
vis[x]=1;for(int i=hed[x];i;i=nxt[i])if(!bridge[i]){
int v=to[i];if(!vis[v])fin_ecc(v,id);
}
idx[x]=id;rnk[x]=(int)ecc[id].size();
ecc[id].push_back(x);
}
vector<int> edge[N];
int f[N][2];
int det[50][50],mull[50];
int s[50][50];
int cal(int sz,int debug=0)//0 to sz
{
// if(debug)cout << sz << endl;
int f=(sz&1)?1:mod-1;
// cout << f << endl;
// if(debug)cout << ":::" << endl;
for(int i=0;i<=sz;i++)for(int j=0;j<=sz;j++){
if(i==j)s[i][j]=det[i][j];
else s[i][j]=mul(det[i][j], mull[i]);
if(debug)if(j==0)cout << mull[i] << ":";
if(debug)cout << s[i][j] << " ";
if(debug)if(j==sz)puts("");
}
for(int i=0;i<=sz;i++){
int p=-1;
for(int j=i;j<=sz;j++)if(s[j][i])p=j;
if(p==-1)return 0;
for(int j=0;j<=sz;j++)swap(s[i][j], s[p][j]);
if(p^i)f=mod-f;
int inv = qpow(s[i][i], mod-2);
for(int j=i+1;j<=sz;j++){
int c = mul(inv, s[j][i]);
if(c)for(int k=i;k<=sz;k++)
s[j][k]=sub(s[j][k], mul(s[i][k], c));
}
}
for(int i=0;i<=sz;i++)f=mul(f,s[i][i]);
if(debug)cout << f << endl;
return f;
}
void construct(int x,int pre){
for(size_t i=0;i<=ecc[x].size();i++){
for(size_t j=0;j<=ecc[x].size();j++)det[i][j]=0;
mull[i]=1;
}
int sz = ecc[x].size();
int TOP = 0;
// cout << x << "----" << endl;
for(size_t i=0;i<ecc[x].size();i++){
int u = ecc[x][i];
// cout << u << " ";
int d0=1,d1=0;
for(int e=hed[u];e;e=nxt[e]){
int v=to[e];
if(idx[v]==x){
det[rnk[u]][rnk[v]]++;
}
else{
if(idx[v]==pre) TOP=rnk[u];
else{
// mull[rnk[u]]=mul(mull[rnk[u]],f[idx[v]][0]);
d1=add(mul(d1,f[idx[v]][0]),mul(d0,f[idx[v]][1]));
d0=mul(d0,f[idx[v]][0]);
}
}
}
mull[rnk[u]]=d0;
det[rnk[u]][rnk[u]]=d1;
}
// puts("");
// cout << x << "---" << endl;
f[x][0]=cal(sz-1,0);
det[sz][sz]=0;
det[TOP][sz]=det[sz][TOP]=1;
f[x][1]=sub(0,cal(sz,0));
// cout << x << ":" << f[x][0] << ":" << f[x][1] << endl;
}
inline void dp(int x,int pre){
for(size_t i=0;i<edge[x].size();i++){
int v=edge[x][i];if(v==pre)continue;
dp(v,x);
}
construct(x,pre);
}
int Type;
int main()
{
cin >> n >> m >> Type;
for(int i=1;i<=m;i++){
int u,v;scanf("%d%d",&u,&v);
adde(u,v),adde(v,u);
}
tarjan(1,0);
for(int i=1;i<=n;i++)if(!vis[i]){
fin_ecc(i,++ccnt);
}
for(int i=2;i<=cnt;i++){
if(bridge[i]){
edge[idx[from[i]]].push_back(idx[to[i]]);
}
}
dp(1,0);
printf("%d
",(n&1)?sub(0,f[1][0]):f[1][0]);
}