[氧化镍]神迹再临

[氧化镍]神迹再临

题目

题目描述
T i w sf Tiw Tiw 又双叒叕在 A K AK AK 虐场了！作为 T L Y sf TLY TLY 太阳神教 的狂热信徒，我们当然要去围观。

具体而言，这个城市有 n n n 个学校排成一列。一共有 m m m 天，第 i i i 天 T i w sf Tiw Tiw 会 A K AK AK 两场比赛，上午在学校 l i l_i li​，下午在学校 r i ( l i ≤ r i ) r_i;(l_ile r_i) ri​(li​≤ri​) 。而我们这 m m m 天会选择同一个观摩方案：上午从左往右，参观学校 1 1 1 到学校 x x x 进行的比赛；下午从右往左，参观学校 n n n 到学校 y y y 的比赛。

由于我们想见证一个特殊的时刻——神迹再临，我们必须某一天的两场 A K AK AK 都观摩到，才能称这一天为 g o o d d a y rm good;day goodday 。显然 x , y x,y x,y 的值不同时，我们的 g o o d d a y rm good;day goodday 数量不同。到底怎么选才好呢？我们列了一个矩阵出来， A x , y ( x ≤ y ) A_{x,y};(xle y) Ax,y​(x≤y) 是选择 x , y x,y x,y 时 g o o d d a y rm good;day goodday 的数量。

结果这个矩阵被 T L Y sf TLY TLY 海神教 的大主教看到了！他非常生气，准备联合 T L Y sf TLY TLY 大地之神教 的大主教，对我们进行制裁！当然信息传递需要隐秘，所以他决定计算出这个矩形的行列式，作为一个暗示。但是这个矩阵是上三角矩阵，太简单了，于是他先把这个矩形沿主对角线进行了对称，即令 A y , x = A x , y ( x ≤ y ) A_{y,x}=A_{x,y};(xle y) Ay,x​=Ax,y​(x≤y)，然后再计算行列式，对 998244353 998244353 998244353 取模。

哈哈哈，我们知道你需要传递的值是什么！不妨让我亲口告诉你吧。难道我们会怕你么？

—— T L Y sf TLY TLY 太阳神教 永放光辉！

数据范围与提示
m ≤ n + 300 ≤ 5 × 1 0 5 mle n+300le 5times 10^5 m≤n+300≤5×105 。

思路

原问题是， m m m 个区间 [ l i , r i ] [l_i,r_i] [li​,ri​]，令 A x , y A_{x,y} Ax,y​ 为所有包含元素 x , y x,y x,y 的区间的数量。显然二者等价。

一个很重要的信息是：一个矩阵的行列式与其高维差分矩阵的行列式相同。因为差分的本质就是一行减去另一行，一列减去另一列。

而 [ l i , r i ] [l_i,r_i] [li​,ri​] 提供的贡献就是一个子矩形 x , y ∈ [ l i , r i ] x,yin[l_i,r_i] x,y∈[li​,ri​] 。进行高维差分，就成了 a l i , l i a_{l_i,l_i} ali​,li​​ 和 a r i + 1 , r i + 1 a_{r_i+1,r_i+1} ari​+1,ri​+1​ 加一， a l i , r i + 1 , a r i + 1 , l i a_{l_i,r_i+1},a_{r_i+1,l_i} ali​,ri​+1​,ari​+1,li​​ 减一。

你发现它很像 基尔霍夫矩阵。它就是 l i ↔ r i + 1 l_ileftrightarrow r_i+1 li​↔ri​+1 这条边的对应值。更巧妙的是：当 r i = n r_i=n ri​=n 时，它所贡献到的第 n + 1 n+1 n+1 行、第 n + 1 n+1 n+1 列被抹去了。所以说：这个行列式就是生成树个数！

然后你看到 m ≤ n + 300 mle n+300 m≤n+300 这一条件，哈哈，稀疏图！一个套路的做法是，去掉所有一度点，缩掉所有二度链：若有条二度链 a → ⋯ → b arightarrowcdotsrightarrow b a→⋯→b，那么 a , b a,b a,b 要么在生成树中通过这条链相连，要么这条链上恰好一条边是非生成树边。所以用一条边 a → b arightarrow b a→b 来代替它，选它的贡献是 1 1 1，不选的贡献是 l e n len len 。提前将答案乘 l e n len len 后，就变成了带权 1 l e n 1over len len1​ 的经典矩阵树定理。

那么此时图中每个点的度数都至少为 3 3 3 。我们来康康，最多有多少个点呢？随便构建出一颗生成树，显然度数之和为 2 ( n − 1 + f ) 2(n-1+f) 2(n−1+f)，其中 f f f 为非树边数量。而我们知道，每个点的度数至少为 3 3 3，所以总度数至少是 3 n 3n 3n 。于是有 2 ( n − 1 + f ) ≥ 3 n 2(n-1+f)ge 3n 2(n−1+f)≥3n，进而有 n ≤ 2 f − 2 nle 2f-2 n≤2f−2 。

而我们的转化中，并没有让非树边的数量变多（一度点是必然树边；二度链中恰好有一个非树边，则新边为非树边，否则都是树边），于是 f = m − ( n − 1 ) f=m-(n-1) f=m−(n−1) 。

也就是说，新图中只有最多 2 ( m − n ) 2(m-n) 2(m−n) 个点！那么此时再用矩阵树定理，就是 O [ ( m − n ) 3 ] mathcal O[(m-n)^3] O[(m−n)3] 的了，足以通过本题。

代码

注意二度点构成环的情况。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long int_;
inline int readint(){int a = 0; char c = getchar(), f = 1;for(; c<'0'||c>'9'; c=getchar())if(c == '-') f = -f;for(; '0'<=c&&c<='9'; c=getchar())a = (a<<3)+(a<<1)+(c^48);return a*f;
}const int Mod = 998244353;
inline void add(int &x,const int &y){(x += y) >= Mod ? (x -= Mod) : 0;
}
inline int qkpow(int_ b,int q){int a = 1;for(; q; q>>=1,b=b*b%Mod)if(q&1) a = a*b%Mod;return a;
}const int MaxN = 500005;
vector<int> G[MaxN];
int deg[MaxN];
void adjust(int x){if(deg[x] != 1) return ;deg[x] = 0; // die outfor(int y : G[x])-- deg[y], adjust(y);
}bool vis[MaxN];
void bfs(int x,int pre = 0){if(vis[x]) return ; else vis[x] = 1;for(int y : G[x]) bfs(y,x);
}
int dfs(int x,int pre,int &dis){if(vis[x]) return -1;++ dis; vis[x] = true;for(int y : G[x]){if(y == pre) continue;if(deg[y] <= 0) continue;if(deg[y] != 2) return y;return dfs(y,x,dis);}return -2; // isolated(leaf)
}struct Edge{int from, to, val;Edge(int F,int T,int V){from = F, to = T, val = V;}
};
vector<Edge> edges;
int haxi[MaxN], a[305][305];
int gauss(int n){for(auto e : edges){e.from = haxi[e.from];e.to = ];add(a[e.from][e.from],e.val);add(][e.to],e.val);add(a[e.from][e.to],Mod-e.val);add(][e.from],Mod-e.val);}-- n; // ignore thisint res = 1, f = 1;for(int i=1,id=0; i<=n; ++i){rep(j,i,n) a[j][i] ? (id = j) : 0;if(!a[id][i]) return 0;if(id != i) res = -res,swap(a[id],a[i]);rep(j,i+1,n){if(!a[j][i]) continue;drep(k,n,i)a[j][k] = (1ll*a[j][k]*a[i][i]+Mod-1ll*a[i][k]*a[j][i]%Mod)%Mod;f = 1ll*f*a[i][i]%Mod;}res = 1ll*res*a[i][i]%Mod;}return 1ll*(res+Mod)*qkpow(f,Mod-2)%Mod;
}int inv[MaxN];
void prepare(int n){rep(i,(inv[1]=1)<<1,n)inv[i] = (0ll+Mod-Mod/i)*inv[Mod%i]%Mod;
}
int main(){int n = readint(), m = readint();for(int i=1; i<=m; ++i){int l = readint(), r = readint();G[l].push_back(r+1);G[r+1].push_back(l);}prepare(++ n), bfs(1);rep(i,1,n) // quick checkif(!vis[i])return puts("0")*0;else vis[i] = false;rep(i,1,n) deg[i] = G[i].size();rep(i,1,n) adjust(i); // kill one-degint ans = 1, tot = 0;for(int i=1; i<=n; ++i)if(!vis[i] && deg[i] == 2){int dis = 0, a = 0, b = 0;for(int x : G[i]){if(deg[x] <= 0) continue;if(!a) a = dfs(i,x,dis);else b = dfs(i,x,dis);vis[i] = false; // avoid errorif(a == -1 || b == -1)return printf("%dn",dis)*0;}ans = 1ll*ans*dis%Mod; vis[i] = 1;edges.push_back(Edge(a,b,inv[dis]));}for(int i=1; i<=n; ++i)if(deg[i] > 2){haxi[i] = ++ tot;for(int j : G[i])if(j < i && deg[j] > 2)edges.push_back(Edge(i,j,1));}if(!tot) return printf("%dn",ans)*0;ans = 1ll*ans*gauss(tot)%Mod;printf("%dn",ans);return 0;
}