题面

n

n

n 个点，

m

m

m 条边。

1

≤

n

≤

1

0

5

,

n

−

1

≤

m

≤

2

×

1

0

5

1\leq n\leq 10^5,n-1\leq m\leq 2\times10^5

1≤n≤105,n−1≤m≤2×105 。

题解

直接求行列式是不现实的，我们可以通过行列式的定义式来思考解法。

一个会产生贡献的排列，相当于要每个点选一个邻接点当爹，每个点的爹必须不一样。

如果这个点度为 1，那么它和它的邻接点必须配对，然后相当于删掉了。同时这两个点使得该排列的贡献乘上 -1 。类推下去，很容易就能解决一棵树的情况，或者剪掉该图所有枝杈。

然后对于一个干干净净的环，则只有两个大方向：要么相邻的两两配对，要么朝向同一个方向认爹。相邻的配对，总点数只能是偶数，总共两种方案，每个方案的每一对都要使排列贡献乘上 -1，所以总共会使排列的贡献乘上

2

×

(

−

1

)

总

点

数

/

2

2\times(-1)^{总点数/2}

2×(−1)总点数/2 。朝同一个方向认爹，也有两种方案，顺时针和逆时针，每种方案的贡献都是

(

−

1

)

总

点

数

−

1

(-1)^{总点数-1}

(−1)总点数−1 （你想想就知道了），两种方案总共会使排列的贡献乘上

2

×

(

−

1

)

总

点

数

−

1

2\times(-1)^{总点数-1}

2×(−1)总点数−1 。

把这两种模式合并起来怎么办呢？

你可以暴力拓扑删点拆环统计贡献……

也可以用比较清晰的DP做法，在仙人掌上 DP ，建一个圆方树做树形DP。

不过具体的 DP 流程还是根暴力删点拆环差不多

时间复杂度

O

(

n

)

O(n)

O(n) 。

CODE

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<random>
#include<vector>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 200005
#define LL long long
#define ULL unsigned long long
#define DB double
#define lowbit(x) (-(x) & (x))
#define ENDL putchar('\n')
#define FI first
#define SE second
LL read() {
    LL f=1,x=0;int s = getchar();
    while(s < '0' || s > '9') {if(s<0)return -1;if(s=='-')f=-f;s = getchar();}
    while(s >= '0' && s <= '9') {x = (x<<3) + (x<<1) + (s^48); s = getchar();}
    return f*x;
}
void putpos(LL x) {if(!x)return ;putpos(x/10);putchar('0'+(x%10));}
void putnum(LL x) {
    if(!x) {putchar('0');return ;}
    if(x<0) {putchar('-');x = -x;}
    return putpos(x);
}
void AIput(LL x,int c) {putnum(x);putchar(c);}

const int MOD = 993244853;
int n,m,s,o,k;
int ind[MAXN];
int hd[MAXN],v[MAXN<<1],nx[MAXN<<1],cne;
void ins(int x,int y) {
    ind[y] ++;
    nx[++ cne] = hd[x]; v[cne] = y; hd[x] = cne;
}
vector<int> g[MAXN];
bool f[MAXN];
int fa[MAXN];
int d[MAXN],id[MAXN];
void dfs0(int x,int ff) {
    d[x] = d[fa[x] = ff] + 1;
    for(int i = hd[x];i;i = nx[i]) {
        int y = v[i];
        if(y != ff) {
            if(!d[y]) {
                dfs0(y,x);
            }
            else if(d[y] < d[x]) {
                int p = x;
                f[++ n] = 1;
                while(p != y) {
                    id[p] = n;
                    p = fa[p];
                }
                g[n].push_back(y);
                g[y].push_back(n);
            }
        }
    }
    if(id[x]) {
        g[id[x]].push_back(x);
        g[x].push_back(id[x]);
    }
    else {
        g[ff].push_back(x);
        g[x].push_back(ff);
    }
    return ;
}
int dp[MAXN][2];
bool df[MAXN];
int tmp[MAXN],tp,tmd[MAXN];
void dfs(int x,int ff) {
    if(f[x]) {
        int dpp = 1;
        for(int i = 0;i < (int)g[x].size();i ++) {
            int y = g[x][i];
            if(y != ff) {
                dfs(y,x);
                dpp = dpp *1ll* dp[y][1] % MOD;
            }
        }
        tp = 0;
        int ad = 0;
        for(int i = 0;i < (int)g[x].size();i ++) {
            int y = g[x][i];
            tmp[tp ++] = y;
            if(y == ff) ad = tp-1;
        }
        int D[2][2] = {};
        D[0][0] = 1;
        D[1][1] = 1;
        for(int i = (ad+1)%tp;i != ad;i = (i+1)%tp) {
            int y = tmp[i];
            for(int j = 0;j < 2;j ++) {
                int A = (MOD- D[j][1]*1ll*dp[y][1] % MOD + D[j][0]*1ll*dp[y][0] % MOD) % MOD;
                int B = D[j][0]*1ll*dp[y][1] % MOD;
                D[j][0] = A;
                D[j][1] = B;
            }
        }
        int A = 0,B = 0;
        (A += D[1][0]) %= MOD;
        (B += D[0][0]) %= MOD;
        (A += MOD-D[0][1]) %= MOD;
        dp[x][0] = A;
        dp[x][1] = B;
        if(tp & 1) (dp[x][0] += dpp*2ll % MOD) %= MOD;
        else (dp[x][0] += MOD-dpp*2ll%MOD) %= MOD;
    }
    else {
        dp[x][1] = 1;
        for(int i = 0;i < (int)g[x].size();i ++) {
            int y = g[x][i];
            if(y != ff) {
                dfs(y,x);
                if(!f[y]) {
                    int A = (MOD-dp[x][1] *1ll* dp[y][1] % MOD + dp[x][0]*1ll*dp[y][0]%MOD)%MOD;
                    int B = dp[x][1] *1ll* dp[y][0] % MOD;
                    dp[x][0] = A; dp[x][1] = B;
                }
                else {
                    int A = (dp[x][1] *1ll* dp[y][0] % MOD + dp[x][0] *1ll* dp[y][1]%MOD) % MOD;
                    int B = dp[x][1] *1ll* dp[y][1] % MOD;
                    dp[x][0] = A; dp[x][1] = B;
                }
            }
        }
    }
    return ;
}
int main() {
    freopen("cactus.in","r",stdin);
    freopen("cactus.out","w",stdout);
    n = read();
    m = read();
    for(int i = 1;i <= m;i ++) {
        s = read();o = read();
        ins(s,o);ins(o,s);
    }
    dfs0(1,0);
    dfs(1,0);
    AIput(dp[1][0],'\n');
    return 0;
}