2019CCPC秦皇岛赛区（重现赛）1006 Forest Program

77 阅读 0 评论 51 点赞

我是靠谱客的博主淡然八宝粥，最近开发中收集的这篇文章主要介绍2019CCPC秦皇岛赛区（重现赛）1006 Forest Program，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Problem Description

Z 国近年来一直在考虑遏制国土沙漠化的方案。在 Z 国广阔的疆域上，有着许多的沙漠。沙漠上干旱少雨，荒无人烟，仅有仙人掌能在这种魔鬼环境中生存。经过 Z 国地质探测局的调查，他们得到了沙漠的实地情况。Z 国的地质探测局是一个热爱 CCPC 的机构，他们喜欢使用图论的方式来描述看到的景色。在得到的数据中，沙漠中的每一个连通块都是一棵仙人掌；一个连通块是一棵仙人掌当且仅当连通块中不存在重边和自环，并且每一条边仅被至多一个简单环覆盖。

经过一番评估，Z 国决定通过删去沙漠中的一些边，最终将沙漠变为森林。这里我们定义森林满足：森林中每一个连通块都是一棵树，而树是边数等于点数减一的连通块。现在给定一个包含 n 个点的沙漠，请你求出 Z 国一共有多少种满足要求的沙漠改造方案。两种方案不同当且仅当方案中被删去的边集不同。由于答案可能很大，请将最终答案对 998244353 取模后输出。

Input

多组数据，每组数据第一行输入两个非负整数 n、m，分别表示沙漠中的点数和边数。沙漠中点的编号为 1, 2, ..., n。

对于每组数据的第 2 到第 m+1 行，每行输入两个正整数 u、v，表示沙漠中编号为 u 和编号为 v 的两个点之间有边相连。

1≤T≤3，1≤n≤3×105，m≤5×105，1≤u, v≤n 并且 u≠v。

Hint

样例解释

对于第一组样例，只需要至少删去一条边即可变为森林，故一共有 23−1=7 种方案。

Output

对于每一组数据，输出一行一个非负整数，表示答案对 998244353 取模后的值。

Sample Input

2 3 3 1 2 2 3 3 1 6 6 1 2 2 3 3 1 2 4 4 5 5 2

Sample Output

7 49

Source

642ccpcQHD

思路：dfs找环，2的环边数次幕的乘积再乘2的剩余边的的2次幕就是答案

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define maxn 505005
#define ll long long
#define maxm 2050000
#define mod 998244353
ll n,m,sum,ans,vis[maxn],dfn[maxn];
struct Edge
{
    ll to,next;
}e[maxm];
ll head[maxn],cnt=0;
ll qpow(ll base, ll n)
{
    ll ans = 1;
    while(n)
    {
        if(n&1) ans=(ans%mod)*(base%mod)%mod;
        base = (base%mod) * (base%mod)%mod;
        n/=2;
    }
    return ans%mod;
}
void add(ll u,ll v)
{
    e[cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt++;
}
void init()
{
    memset(vis,0,sizeof(vis));
    memset(dfn,0,sizeof(dfn));
    memset(head,-1,sizeof(head));
    cnt=0;ans=1;
}
void dfs(ll id,ll step,ll fa)
{
    vis[id]=1;dfn[id]=step;
    //printf("u=%lldn",id);
    for(ll i=head[id];i!=-1;i=e[i].next)
    {
        ll v=e[i].to;
        //printf(" v=%lldn",v);
        if(v==fa||vis[v]==2) continue;
        if(vis[v]==1)
        {
            //printf("  v=%lldn",v);
            sum+=(step-dfn[v]+1);
            //printf("%lld ")
            ans*=(qpow(2,step-dfn[v]+1)-1+mod)%mod;
            ans%=mod;
        }
        else dfs(v,step+1,id);
    }
    vis[id]=2;
}
int main()
{
        scanf("%lld %lld",&n,&m);
        init();
        for(ll i=1;i<=m;i++)
        {
            ll u,v;
            scanf("%lld %lld",&u,&v);
            add(u,v);add(v,u);
        }
        for(ll i=1;i<=n;i++)
        {
            if(vis[i]==0) dfs(i,1,-1);
        }
        ans*=qpow(2,m-sum);
        ans%=mod;
        printf("%lldn",ans);
}