本文共 1788 字，大约阅读时间需要 5 分钟。

【题解】

题意：输出删除不同边使得所有连通图上无环的所有可能情况并取模，每条边最多只存在于一个环中。

思路：令环的个数为N，每个环内的边数为ai，总边数为m，则答案为   ，即累乘2^(每个环内的边数)-1再乘上2^(无影响的边的数目)。

这个答案很好得到，但是我们要怎么实现计算出每个环内的边数呢？

我们考虑到每条边最多只存在于一个环中，所以只要我们把一个环中的任意一条边删除并且记录下来，我们就会得到一棵树，那么我们就可以把问题转化成 ---> 求给定一对顶点的树上最短路径问题。那么我们怎么确定这对顶点呢？我们用并查集判断是否成环即可找出这条边，即连接这一对点的边。

【代码】

#include 
   
    using namespace std;typedef long long ll;const int maxn=5e5+10;const ll mod=998244353;int pre[maxn],l[maxn],r[maxn];int vis[maxn];struct Edge{    int to,next;}edge[maxn*2];int Find(int x){    return pre[x]==x?x:pre[x]=Find(pre[x]);}int head[maxn],tot;void addedge(int u,int v){    edge[tot].to=v;    edge[tot].next=head[u];    head[u]=tot++;}int fa[maxn][20];int deg[maxn];void bfs(int root){    queue 
    
      que;    deg[root]=0;    fa[root][0]=root;    que.push(root);    while(!que.empty()){        int tmp=que.front();        que.pop();        for(int i=1;i<20;i++)            fa[tmp][i]=fa[fa[tmp][i-1]][i-1];        for(int i=head[tmp];i!=-1;i=edge[i].next){            int v=edge[i].to;            if(v==fa[tmp][0]) continue;            deg[v]=deg[tmp]+1;            fa[v][0]=tmp;            que.push(v);        }    }}int LCA(int u,int v){    if(deg[u]>deg[v]) swap(u,v);    int hu=deg[u],hv=deg[v];    int tu=u,tv=v;    for(int det=hv-hu,i=0;det;det>>=1,i++)        if(det&1)            tv=fa[tv][i];    if(tu==tv) return tu;    for(int i=19;i>=0;i--){        if(fa[tu][i]==fa[tv][i])            continue;        tu=fa[tu][i];        tv=fa[tv][i];    }    return fa[tu][0];}ll qpow(ll a,ll b){    ll ret=1;    while(b){        if(b&1) ret=ret*a%mod;        a=a*a%mod;        b>>=1;    }    return ret;}int main(){    int n,m;    while(~scanf("%d%d",&n,&m)){        tot=0;        for(int i=1;i<=n;i++)            pre[i]=i,head[i]=-1;        int cnt=0;        for(int i=0;i
    
   

转载地址：http://nhfen.baihongyu.com/