自助建站系统介绍,佛山seo技术,网站如何做质保系统,网站策划哪里找毒瘤题#x1f605;
简单版本 CF235D Graph Game
首先#xff0c;考虑建立圆方树#xff0c;然后对于一个点双#xff08;简单环#xff09;上的两个点#xff0c;有两条路径可以到达
和简单版本类似#xff0c;考虑容斥。即枚举点对 i , j i,j i,j之间 哪些路径是联…毒瘤题
简单版本 CF235D Graph Game
首先考虑建立圆方树然后对于一个点双简单环上的两个点有两条路径可以到达
和简单版本类似考虑容斥。即枚举点对 i , j i,j i,j之间 哪些路径是联通的 记固定下来的路径的并为 A A A则 i , j i,j i,j之间通过 A A A联通的概率为 1 ∣ A ∣ \frac{1}{|A|} ∣A∣1。
然后就是神来之笔了设 A A A中有 c n t cnt cnt个环则容斥系数为 ( − 1 ) c n t (-1)^{cnt} (−1)cnt。证明考虑 i , j i,j i,j之间实际有 k k k个环则这个方案被计算了 ∑ x ≤ k 2 x ( k x ) ( − 1 ) k − x ( 2 − 1 ) k 1 \sum_{x\le k}2^x\binom{k}{x}(-1)^{k-x}(2-1)^k1 ∑x≤k2x(xk)(−1)k−x(2−1)k1次。
考虑在圆方树上 D P DP DP。因为点对之间的 L C A LCA LCA可能是方点或者圆点因此不好统计。可以考虑直接枚举其中一个点然后跑 D F S DFS DFS复杂度 O ( n 3 ) O(n^3) O(n3)。
#includebits/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 mod998244353;
const int N805;
int n,m,tot;
vectorintG[N];
int dfn[N],low[N],ps[N][N],num;
ll res;
stackints;
vectorintG2[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 tmp0,d0;tot,G2[u].pb(tot),G2[tot].pb(u),ps[tot][u]d;do{tmps.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 ymod-2){ll z(1);for(;y;y1){if(y1)zz*x%mod;xx*x%mod;}return z;
}
ll f[N][N],fac[N],inv[N],invnum[N];
void init(int n){fac[0]1;for(int i1;in;i)fac[i]fac[i-1]*i%mod;inv[n]fpow(fac[n]);for(int in;i1;i--)inv[i-1]inv[i]*i%mod;for(int i1;in;i)invnum[i]inv[i]*fac[i-1]%mod;
}
void add(ll x,ll y){x(xy)%mod;
}
int sz[N];
void dfs(int u,int topf,int sz){for(int i1;isz;i){if(f[u][i])add(res,invnum[i]*f[u][i]);}for(auto e:G2[u]){if(etopf)continue;for(int i0;iG2[e].size();i){if(ips[e][u])continue;int vG2[e][i],l1abs(ps[e][u]-ps[e][v])-1,l2G2[e].size()-2-l1;for(int i1;isz;i){add(f[v][il11],f[u][i]);add(f[v][il21],f[u][i]);add(f[v][il1l21],-f[u][i]);}dfs(v,e,szl1l21);}}
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cinnm,init(n),totn;for(int i1;im;i){int x,y;cinxy;G[x].pb(y),G[y].pb(x);}tarjan(1);for(int i1;in;i){memset(f,0,sizeof f),f[i][1]1,dfs(i,-1,1); }cout(resmod)%mod;
}
