BZOJ4784 [Zjoi2017]仙人掌

标签:树形DP,tarjan,仙人掌

题目

题目传送门

Description
如果一个无自环无重边无向连通图的任意一条边最多属于一个简单环,我们就称之为仙人掌。所谓简单环即不经过重复的结点的环。

现在九条可怜手上有一张无自环无重边的无向连通图,但是她觉得这张图中的边数太少了,所以她想要在图上连上一些新的边。同时为了方便的存储这张无向图,图中的边数又不能太多。经过权衡,她想要加边后得到的图为一棵仙人掌。不难发现合法的加边方案有很多,可怜想要知道总共有多少不同的加边方案。两个加边方案是不同的当且仅当一个方案中存在一条另一个方案中没有的边。

Input

多组数据,第一行输入一个整数T表示数据组数。

每组数据第一行输入两个整数n,m,表示图中的点数与边数。

接下来m行,每行两个整数u,v(1≤u,v≤n,u!=v)表示图中的一条边。保证输入的图联通且没有自环与重边

Sigma(n)<=5*10^5,m<=10^6,1<=m<=n * (n-1)/2

Output

对于每组数据,输出一个整数表示方案数,当然方案数可能很大,请对998244353取模后
输出。

Sample Input

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

Sample Output

2
8

对于第一组样例合法加边的方案有 {}, {(2,3)},共 2 种。

题意

给定一个无向连通图,添加一些边,使其变为仙人掌

问方案数

分析

我大概。。。只会写10分暴力+20分特判吧


正解如下

首先特判这张图是否是仙人掌,如果是,那么输出0

显然环是对答案不产生贡献的,那么破环为链

这样原图转化成一棵树,部分分设置的用意如此

用h[i]表示有i个点,它们之间匹配的方案数

h[i]=h[i-1]+(i-1)*h[i-2]

  • 如果i节点不与其他节点相连,那么方案就是h[i−1]
  • 如果与其他节点连接,那么有(i−1)中选择方式,而当选择一个点以后,有两个点不能再连接,那么方案就是(i−1)∗h[i−2]

用f[i]表示子树i的方案数,g[i]表示可向上拓展的子树的方案数,num表示子树的节点个数(即大小)

f[i]=h[num]g[son](sonChild(i)) f [ i ] = h [ n u m ] ∗ ∏ g [ s o n ] ( s o n ∈ C h i l d ( i ) )

每一个子节点都可以向上扩展并相对独立,然后一共有h[num]种儿子的匹配方案

g[i]=f[i]+h[num1]numg[son](sonChild(i)) g [ i ] = f [ i ] + h [ n u m − 1 ] ∗ n u m ∗ ∏ g [ s o n ] ( s o n ∈ C h i l d ( i ) )

该节点可以自己想上扩展为f[i],并且有num个子节点,每个子节点还可以选择一个儿子,并且一共有h[num-1]种匹配方案

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{ll f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
const int mod=998244353,maxn=5e5+6,maxm=1e6+6;
struct edge{int to,next,from;}e[maxm*2];
bool isca,vis[maxn],flag[maxm*2];ll f[maxn],g[maxn],h[maxn],ans;
int que[maxn],dfn[maxn],low[maxn],col[maxn],tim,top,T,n,m,cnt,last[maxn];
void insert(int u,int v){e[++cnt]=(edge){v,last[u],u};last[u]=cnt;flag[cnt]=1;e[++cnt]=(edge){u,last[v],v};last[v]=cnt;flag[cnt]=1;
}
void tarjan(int x,int fa){bool flag=0;dfn[x]=low[x]=++tim;que[++top]=x;reg(x){if(e[i].to==fa)continue;if(!dfn[e[i].to]){tarjan(e[i].to,x);low[x]=min(low[x],low[e[i].to]);if(low[e[i].to]<dfn[x]){if(flag){isca=0;return;}flag=1;}}else{low[x]=min(low[x],dfn[e[i].to]);if(dfn[e[i].to]<dfn[x]){if(flag){isca=0;return;}flag=1;}}}if(low[x]==dfn[x])while(true){col[que[top--]]=x;if(que[top+1]==x)break;}
}
void dfs(int x,int fa){vis[x]=1;f[x]=1,g[x]=0;int num=0;reg(x){if(!flag[i]||e[i].to==fa)continue;dfs(e[i].to,x);f[x]=f[x]*g[e[i].to]%mod;num++;}g[x]=(f[x]*h[num]%mod+f[x]*h[num-1]%mod*num%mod)%mod;f[x]=f[x]*h[num]%mod;
}
int main()
{h[0]=h[1]=1;rep(i,2,maxn-5)h[i]=(h[i-1]+(h[i-2]*(i-1)%mod))%mod;T=read();while(T--){isca=1,ans=1;cnt=tim=top=0;n=read(),m=read();rep(i,1,n){vis[i]=0;last[i]=col[i]=dfn[i]=low[i]=0;}rep(i,1,m){int u=read(),v=read();insert(u,v);}tarjan(1,0);if(!isca){printf("0\n");continue;}rep(i,1,cnt)if(col[e[i].from]==col[e[i].to])flag[i]=0;rep(i,1,n){if(vis[i])continue;dfs(i,0);ans=ans*f[i]%mod;}printf("%lld\n",ans);}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/40585.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

如何绘制一组创意的仙人掌图标

创建新的项目文件 启动并在后台运行Illustrator&#xff0c;创建新文档&#xff08;文件>新建或Control-N&#xff09; 画板数量&#xff1a;1 宽度&#xff1a; 800像素 高度&#xff1a; 600像素 单位&#xff1a; 像素 进入“高级”选项卡&#xff1a; 色彩模式&a…

大量短信群发?不妨来看看这几个平台

最近在跟着公司一块做一个新的项目&#xff0c;刚好我做到注册登录的模块&#xff0c;一个需要短信群发的功能&#xff0c;没有过多的精力去写短信验证码模块&#xff0c;便找了几个比较好用的API短信接口平台&#xff1b;在这里给大家列举几个不同的平台&#xff0c;希望能帮到…

短信平台不知道怎么选?来看看这几个平台:

不少程序员在做项目的时候会碰上短信收发验证码的问题&#xff0c;通常来说解决方案有二&#xff0c;要么自己写一个验证码模块儿&#xff0c;要么去找短信平台。但自己写一个验证码模块是出了名的麻烦&#xff0c;而且会耗费掉不少时间&#xff0c;有着时间到不如优化下自己的…

【chatgpt代码系列】雷达转点云算法沟通记录

AI作为一个强大的生产力工具&#xff0c;怎么使用它才能快速结合我们自己的工作呢&#xff1f;下面是我的探索&#xff0c;目前来看&#xff0c;是可以代替百度谷歌等搜索引擎的一部分作用&#xff0c;加入到我的工作流当中。

重磅!openAI开放chatGPT模型APIgpt-3.5-turbo,成本直降90%!

ChatGPT API&#xff0c;千呼万唤终于来了。 chatGPT不仅开放 成本还直降90%&#xff01; 全新API基于“gpt-3.5-turbo”模型&#xff0c;其基础是支持ChatGPT的GPT 3.5模型&#xff0c;取代了此前的“text-davinci-003.”。这款名为“gpt-3.5-turbo”的模型&#xff0c;定价…

模型量化:PTQ + onnx

8 位线性量化的数学表达 将 32 位浮点(实数)模型转换为 8 位整数模型 F 32 S c a l e ∗ ( I i n t 8 − Z ) 量化公式&#xff1a; I i n t 8 F 32 S c a l e Z F_{32} Scale * (I_{int8}-Z)\\ 量化公式&#xff1a; I_{int8} \frac{F_{32}}{Scale} Z F32​Scale∗(Ii…

模型量化

https://zhuanlan.zhihu.com/p/132561405 模型量化是一种将浮点计算转成低比特定点计算的技术&#xff0c;可以有效的降低模型计算强度、参数大小和内存消耗&#xff0c;但往往带来巨大的精度损失。尤其是在极低比特(<4bit)、二值网络(1bit)、甚至将梯度进行量化时&#xf…

量化模型

量化模型&#xff08;Quantized Model&#xff09;是一种模型加速&#xff08;Model Acceleration&#xff09;方法的总称&#xff0c;包括二值化网络&#xff08;Binary Network&#xff09;、三值化网络&#xff08;Ternary Network&#xff09;&#xff0c;深度压缩&#xf…

读取锁信息失败(8):该账户当前被锁定,所以用户 ‘sa‘ 登录失败。

读取锁信息失败(8)&#xff1a;该账户当前被锁定&#xff0c;所以用户 sa 登录失败。系统管理员无法将该账户解锁。 State:37000,Native:18486,Origin:[Microsoft][ODBC SQL Server Driver][SQL Server] 打开软件提示上面的信息 此问题是由于sa账户在同一时间被多次登录&#x…

Oracle连接账户被锁:the account is locked 的解决办法

Oracle连接账户被锁&#xff1a;the account is locked 问题背景 在做配置文件数据库密码加密时&#xff0c;没注意做了一些骚操作&#xff0c;导致数据库被锁&#xff0c;网上找的资料都试了个遍&#xff0c;还是没用。浪费了两三个小时&#xff0c;差点都卸载重装数据库了。…

oracle提示“记录被另外一个用户锁定“

问题描述&#xff1a; 某人对某一条数据进行了修改&#xff0c;oracle会通过这个事务记住这条数据&#xff0c;若修改的人没有进行提交或进行回滚记录&#xff0c;oracle是不允许对这条数据在此进行修改的&#xff0c;在这种情况下你要进行修改数据&#xff0c;则会被阻止&…

ORACLE数据库 某用户账户被锁定问题解决

遇到的问题&#xff1a; [realestate][ERROR] [2022-05-17 14:27:11] com.alibaba.druid.pool.DruidDataSource$CreateConnectionThread.run(2469) | create connection SQLException, url: jdbc:p6spy:oracle:thin:172.18.13.83:1521/orclxj, errorCode 28000, state 99999 j…

Oracle账户被锁定后如何解锁

**原因&#xff1a;** 今天拉取了新的代码后&#xff0c;由于oracle数据库的配置忘记了更改&#xff0c;启动项目时一直连接不上数据库&#xff0c;改了两次后还是连接不上&#xff0c;最后只能启动一下没拉取代码前的项目&#xff0c;发现报了一个账户被锁定 ![在这里插入图片…

【饭谈】坚守自己的职业规划,给自己留一张底牌吧。

最近想必大家都被新出的chatGPT吓坏了吧&#xff1f;各种机构和博主跟风似的疯狂说gpt多厉害&#xff0c;会取代多少人&#xff0c;导致多少人下岗&#xff0c;各种Ai测试兴起等贩卖焦虑的言论。获得了很多的流量&#xff0c;也变现了很多。但却给全行业的打工人带来了恐惧心理…

深度:从工业救国到数字化兴国!

‍数据智能产业创新服务媒体 ——聚焦数智 改变商业 昨天&#xff0c;发生了两件事情&#xff0c;一喜一悲&#xff0c;喜的是颁布了《数字中国建设整体布局规划》&#xff1b;悲的是“改革先锋”厉以宁先生离开了我们。将这两件事情结合起来&#xff0c;让我们思考一个问题—…

AI大模型,救了 “低代码” 的命

作者| Mr.K 编辑| Emma 来源| 技术领导力(ID&#xff1a;jishulingdaoli) 著名技术哲学家安德鲁•费恩伯格教授&#xff0c;曾提过一个很有创意的概念&#xff0c;“技术民主化”。教授认为&#xff0c;技术民主就是扩大社会个体的自由边界&#xff0c;让大家积极有效地参与到…

NVIDIA市值破万亿,回顾黄仁勋台大毕业典礼发表演说

夕小瑶科技说 分享 作者 | 黄仁勋 来源 | 芯榜、Datawhale干货 黄仁勋台大毕典演说全文。无论是追逐食物、或不被人当食物&#xff0c;你都要不停跑下去。 黄仁勋受邀参加台大毕业典礼。他出生于台南&#xff0c;4 岁时随家人离开台湾&#xff0c;前往美国。 摘要 英伟达&…

5个最喜欢的提示词技巧;如何制定企业的生成式AI战略;胎教级SD详细使用教程;ChatGPT不是万能的6个证据 | ShowMeAI日报

&#x1f440;日报&周刊合集 | &#x1f3a1;生产力工具与行业应用大全 | &#x1f9e1; 点赞关注评论拜托啦&#xff01; &#x1f916; 6月AI相关网站访问量统计&#xff0c;9大类目应用 Top5 清单 这是 AceCamp 通过 SimilarPro 统计的6月份AI相关网站的访问量&#xff…

英伟达创办人黄仁勋台大毕典演说全文

省时查报告-专业、及时、全面的行研报告库 省时查方案-专业、及时、全面的营销策划方案库 【免费下载】2023年4月份热门报告合集 省时科技ChatGPT发布&#xff0c;无需翻墙&#xff0c;无需注册直接使用 马斯克谈AI&#xff1a;中美差距12个月&#xff0c;出现AGI只要三五年 万…

群晖NAS 7.X 搭建个人博客网站并发布公网 4/8

系列文章 群晖NAS 7.X 搭建个人博客网站并发布公网 1/8群晖NAS 7.X 搭建个人博客网站并发布公网 2/8群晖NAS 7.X 搭建个人博客网站并发布公网 3/8群晖NAS 7.X 搭建个人博客网站并发布公网 4/8群晖NAS 7.X 搭建个人博客网站并发布公网 5/8群晖NAS 7.X 搭建个人博客网站并发布公…