Description
Input
Output
Sample Input
样例 1 输入:
2
3 2
1 2
2 3
Sample Output
样例 1 输出:
665496241
Data Constraint
Hint
思路
树上一条路径可行的概率是1/len.（len个点，第一个点要第一个选到）
环上做一个容斥：路径A可行+路径B可行-路径AB均可行。
仙人掌上做dp容斥即可。
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 998244353,N = 477;
int n,m;
ll fac[N],unfac[N],inv[N];
ll power(ll x,ll y)
{
ll ret = 1;
for(; y; y >>= 1)
{
if (y & 1) ret = ret * x % mod;
x = x * x % mod;
}
return ret;
}
int len[N];
ll f[N][N];
int no[N],cir[N],cnt,cirbel[N];
int ls[N],nx[N * 8],to[N * 8],tot = 1;
void add(int x,int y) {
to[++tot] = y,nx[tot] = ls[x],ls[x] = tot;
}
int dfn[N],stm,p[N],e[N * 8];
int cirfa[N],dep[N];
void dfs(int x) {
dfn[x] = ++ stm;
for(int i = ls[x]; i; i = nx[i]) {
if (i == p[x]) continue;
int y = to[i];
if (dfn[y] == 0) {
p[y] = i ^ 1;
dep[y] = dep[x] + 1;
dfs(y);
} else if(dfn[y] < dfn[x]) {
e[i] = e[i ^ 1] = 1;
++cnt;
for(int z = x,w = 1; z != y; z = to[p[z]],w++) {
no[z] = w;
len[z] = dep[x] - dep[y] + 1;
add(z,y),add(y,z);
e[p[z]] = e[p[z] ^ 1] = 1;
cirfa[z] = y;
cirbel[z] = cnt;
}
}
}
}
ll ans;
void work(int x,int from) {
for(int i = 1; i <= n; i ++) {
ans = (ans + inv[i] * f[x][i]) % mod;
}
for(int i = ls[x]; i; i = nx[i]) if (e[i] == 0) {
int y = to[i];
if (y == from) continue;
if (y != cirfa[x] && cirfa[y] != x) {
for(int i = 1; i <= n; i++) f[y][i] = f[x][i - 1];
work(y,x);
} else {
int ori = 0,a = 0,b = 0,cirlen = 0;
if (cirfa[x] == y) {
ori = x,a = no[x],b = len[x] - no[x],cirlen = len[x];
} else {
if (cirbel[y] == cirbel[from]) {
cirlen = len[y];
ori = from,a = (no[from] - no[y] + len[y]) % cirlen,b = cirlen - a;
} else {
ori = x,a = no[y],b = len[y] - no[y],cirlen = len[y];
}
}
for(int i = 1; i <= n; i++) {
if (i - a > 0) f[y][i] = f[ori][i - a];
if (i - b > 0) f[y][i] = (f[y][i] + f[ori][i - b]) % mod;
if (i - cirlen + 1 > 0) f[y][i] = (f[y][i] - f[ori][i - cirlen + 1]) % mod;
}
work(y,x);
}
}
}
int main() {
freopen("falldream.in","r",stdin);freopen("falldream.out","w",stdout);
cin >> n >> n >> m;
for(int i = 1; i <= m; i++) {
int x,y; scanf("%d %d",&x,&y);
add(x,y),add(y,x);
}
dfs(1);
fac[0] = 1;
for(int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
unfac[n] = power(fac[n],mod - 2);
for(int i = n - 1; ~i; i--) unfac[i] = unfac[i + 1] * (i + 1) % mod;
for(int i = 1; i <= n; i++) inv[i] = unfac[i] * fac[i - 1] % mod;
for(int r = 1; r <= n; r++)
{
memset(f,0,sizeof f);
f[r][1] = 1;
work(r,0);
}
cout << (ans + mod) % mod << endl;
}