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

毒瘤题😅

简单版本 CF235D Graph Game

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

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

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

考虑在圆方树上 $D P$ 。因为点对之间的 $L C A$ 可能是方点或者圆点，因此不好统计。可以考虑直接枚举其中一个点，然后跑 $D FS$ ，复杂度 $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;
}