【学习笔记】LOJ #6240. 仙人掌

毒瘤题😅

简单版本 CF235D Graph Game

首先，考虑建立圆方树，然后对于一个点双（简单环）上的两个点，有两条路径可以到达

和简单版本类似，考虑容斥。即枚举点对$i,j$之间 哪些路径是联通的 ，记固定下来的路径的并为$A$，则$i,j$之间通过$A$联通的概率为$\frac{1}{|A|}$。

然后就是神来之笔了：设$A$中有$cnt$个环，则容斥系数为$(-1{)}^{cnt}$。证明：考虑$i,j$之间实际有$k$个环，则这个方案被计算了${\sum }_{x\le k}{2}^x\left(\genfrac{}{}{0ex}{}{k}{x}\right)(-1{)}^{k-x}=(2-1{)}^k=1$次。

考虑在圆方树上$DP$。因为点对之间的$LCA$可能是方点或者圆点，因此不好统计。可以考虑直接枚举其中一个点，然后跑$DFS$，复杂度$O(n^3)$。

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define db double
using namespace std;
const int mod=998244353;
const int N=805;
int n,m,tot;
vector<int>G[N];
int dfn[N],low[N],ps[N][N],num;
ll res;
stack<int>s;
vector<int>G2[N];
void tarjan(int u){low[u]=dfn[u]=++num,s.push(u);for(auto v:G[u]){if(!dfn[v]){tarjan(v),low[u]=min(low[u],low[v]);if(low[v]>=dfn[u]){int tmp=0,d=0;tot++,G2[u].pb(tot),G2[tot].pb(u),ps[tot][u]=d++;do{tmp=s.top(),s.pop();G2[tot].pb(tmp),G2[tmp].pb(tot),ps[tot][tmp]=d++;}while(tmp!=v);}}else low[u]=min(low[u],dfn[v]);}
}
ll fpow(ll x,ll y=mod-2){ll z(1);for(;y;y>>=1){if(y&1)z=z*x%mod;x=x*x%mod;}return z;
}
ll f[N][N],fac[N],inv[N],invnum[N];
void init(int n){fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;inv[n]=fpow(fac[n]);for(int i=n;i>=1;i--)inv[i-1]=inv[i]*i%mod;for(int i=1;i<=n;i++)invnum[i]=inv[i]*fac[i-1]%mod;
}
void add(ll &x,ll y){x=(x+y)%mod;
}
int sz[N];
void dfs(int u,int topf,int sz){for(int i=1;i<=sz;i++){if(f[u][i])add(res,invnum[i]*f[u][i]);}for(auto e:G2[u]){if(e==topf)continue;for(int i=0;i<G2[e].size();i++){if(i==ps[e][u])continue;int v=G2[e][i],l1=abs(ps[e][u]-ps[e][v])-1,l2=G2[e].size()-2-l1;for(int i=1;i<=sz;i++){add(f[v][i+l1+1],f[u][i]);add(f[v][i+l2+1],f[u][i]);add(f[v][i+l1+l2+1],-f[u][i]);}dfs(v,e,sz+l1+l2+1);}}
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m,init(n),tot=n;for(int i=1;i<=m;i++){int x,y;cin>>x>>y;G[x].pb(y),G[y].pb(x);}tarjan(1);for(int i=1;i<=n;i++){memset(f,0,sizeof f),f[i][1]=1,dfs(i,-1,1); }cout<<(res+mod)%mod;
}