首页 > 其他分享 >CF512D Fox And Travelling 题解--zhengjun

CF512D Fox And Travelling 题解--zhengjun

时间:2023-07-16 23:01:48浏览次数:34  
标签:rt 连通 fa -- 题解 void int CF512D id

计数好题。

首先对于每个连通块独立考虑,最后合并答案。

发现 点数超过 1 的强连通分量一定删不掉。

  • 若连通块中存在 点数超过 1 的强连通分量
    • tarjan 缩点之后,称这些点数超过 1 的强连通分量为关键点;
    • 那么两关键点之间的点也不能删;
    • 于是对于剩下的点直接 dp 即可,由于可删的子树根一定是最后删的,无需考虑其他情况。
  • 若连通块是一颗树
    • 如果还是像刚才这样找个根 dp 一遍的话,有些方案算不进去(因为根有可能不是最后删除的);
    • 所以考虑对于每个点都作为根计算一遍答案,把所有的加在一起;
    • 那么,对于一个删 \(k\) 个点的方案,就被计算了 \(s-k\) 次,\(s\) 为连通块大小,最后除掉即可。特别地,删 \(s\) 个点的方案没有算重。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e2+10,mod=1e9+9;
int n,m;
vector<int>A[N],B[N];
int top,dft,sct,dfn[N],low[N],scc[N],stk[N];
int cnt[N],C[N][N],inv[N];
void init(){
	for(int i=0;i<=n;i++){
		for(int j=C[i][0]=1;j<=i;j++){
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
		}
	}
	inv[1]=1;
	for(int i=2;i<=n;i++)inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;
}
void tarjan(int u,int fa=0){
	dfn[u]=low[u]=++dft,stk[++top]=u;
	for(int v:A[u])if(v^fa){
		if(!dfn[v])tarjan(v,u),low[u]=min(low[u],low[v]);
		else if(!scc[v])low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		sct++;
		do scc[stk[top]]=sct;while(stk[top--]^u);
	}
}
struct zj{
	int n,a[N];
	zj(int _n=0):n(_n){memset(a,0,sizeof a);}
	zj operator * (const zj &x)const{
		zj b(n+x.n);
		for(int i=0;i<=n;i++)
			for(int j=0;j<=x.n;j++)
				b.a[i+j]=(b.a[i+j]+1ll*a[i]*x.a[j]%mod*C[i+j][i])%mod;
		return b;
	}
	zj operator + (const zj &x)const{
		zj b=x;
		for(int i=0;i<=n;i++)
			(b.a[i]+=a[i])%=mod;
		return b;
	}
}ans,f[N];
int rt,vis[N];
void cover(int u,int fa=0){
	if(cnt[u]>1)rt=u;
	vis[u]=1;
	for(int v:B[u])if(v^fa)cover(v,u);
}
int tag[N];
vector<int>id;
bool push(int u,int fa=0){
	int x=cnt[u]>1;
	for(int v:B[u])if(v^fa)x|=push(v,u);
	if(x)id.push_back(u);
	return tag[u]=x;
}
void dfs2(int u,int fa=0){
	f[u].a[0]=1;
	for(int v:B[u])if(v^fa&&!tag[v]){
		dfs2(v,u),f[u]=f[u]*f[v];
	}
	if(!tag[u]){
		f[u].a[f[u].n+1]=f[u].a[f[u].n];
		f[u].n++;
	}
}
void solve1(int rt){
	id.clear();
	push(rt);
	for(int u:id)dfs2(u),ans=ans*f[u];
}
void insert(int u,int fa=0){
	id.push_back(u);
	for(int v:B[u])if(v^fa)insert(v,u);
}
void solve(int u){
	rt=0,cover(u);
	if(rt)solve1(rt);
	else{
		id.clear();
		insert(u);
		zj sum(id.size());
		for(int x:id){
			dfs2(x);
			sum=sum+f[x];
			for(int y:id)f[y]=zj(0);
		}
		int len=id.size();
		for(int i=0;i<len;i++)sum.a[i]=1ll*sum.a[i]*inv[len-i]%mod;
		ans=ans*sum;
	}
}
int main(){
	freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%d%d",&n,&m),init();
	for(int u,v;m--;){
		scanf("%d%d",&u,&v);
		A[u].push_back(v),A[v].push_back(u);
	}
	for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
	for(int u=1;u<=n;u++)for(int v:A[u]){
		if(scc[u]^scc[v]){
			B[scc[u]].push_back(scc[v]);
		}
	}
	for(int u=1;u<=n;u++)cnt[scc[u]]++;
	ans.a[0]=1;
	for(int i=1;i<=sct;i++)if(!vis[i])solve(i);
	for(int i=0;i<=n;i++)printf("%d\n",ans.a[i]);
	return 0;
}

标签:rt,连通,fa,--,题解,void,int,CF512D,id
From: https://www.cnblogs.com/A-zjzj/p/17558781.html

相关文章

  • 数组
    数组一维数组的定义:类型说明符数组名[常量表达式];int[10]注意:定义数组的时候不能动态定义intn;scanf("%d",&n);inta[n];//c语言编译时就要储存一个数组的内存.不运行后期添加数组内存一些书写格式上的问题//遍历下标变量.输出数组for(i=0;......
  • 【DP】01背包与完全背包总结及空间优化
    01背包问题​ 题目描述:有n件物品,每件物品的重量为w[i],价值为c[i]。现在有一个容量为V的背包,问怎么选取物品放入背包,能使得背包内的总价值最大。其中每件物品只能放入一次。​ 样例:n=5,V=8w[i]=3,5,1,2,2c[i]=4,5,2,1,3​ 分析:使用暴力的解法,每件物品分为放......
  • 富爸爸穷爸爸
    工作已经两年了,直到现在才看一些理财方面的书籍,起因是自己的花钱习惯太不好了,不花钱的时候还好,花起来就克制不住,所以工作两年的存款才7W左右。想起来存款自己就很懊悔为什么不节约一点,这样可以多存一点,在需要大额花钱的时候心底不会慌。但是懊悔也没啥用,只能吸取这个教训去看一些......
  • 人工智能自然语言处理:N-gram和TF-IDF模型详解
    人工智能自然语言处理:N-gram和TF-IDF模型详解1.N-gram模型N-Gram是一种基于统计语言模型的算法。它的基本思想是将文本里面的内容按照字节进行大小为N的滑动窗口操作,形成了长度是N的字节片段序列。每一个字节片段称为gram,对所有gram的出现频度进行统计,并且按照事先设......
  • THU训练营预选赛2023
    比赛地址ATag:排列置换遍历排列中每个置换环,找到每个元素需要跳几次才能回到与之相同的元素(最多为环的长度个数)对每个元素所的次数取max点击查看代码//https://tsinghua.contest.codeforces.com/group/sTsHnFxwiH/contest/453495/problem/A#include<iostream>#......
  • aliyun oss对象存储服务的使用和配置
     引入依赖(依赖冲突可使用mavenhelper插件来排除,或者通过启动异常进行判断,或者看官方文档寻找答案) <dependency>   <groupId>com.aliyun.oss</groupId>   <artifactId>aliyun-sdk-oss</artifactId>   <version>3.5.0</version>   <exclusions>  ......
  • 顺序程序设计
    顺序程序设计1.条件表达式条件表达式结合方式自右向左2.Switch语句#include<stdio.h>voidmain(){inta;printf("inputintegernumber:");scanf("%d",&a);switch(a){case1:printf("Monday\n");......
  • CentOS7下安装VSCode,打造shell开发环境
    一,VSCode安装https://code.visualstudio.com/docs/setup/linux二,安装VSCode中各个插件:https://www.zhihu.com/tardis/zm/art/199187317?source_id=1005注意:shell-format插件安装之后,也不能马上工作,需要安装格式化程序到插件目录中,在控制台有提醒,不过,这个并不是最关键的,还有需......
  • 五子棋人机对战
    #include<windows.h>#include<windowsx.h>#include<ShObjIdl.h>#include<cmath>#include<cstdlib>#include<ctime>#include<vector>#include<algorithm>#include<iostream>#include<cstdio>......
  • ASP.NET Core SignalR 系列(四)- 中心筛选器
    本章将和大家分享ASP.NETCoreSignalR中的中心筛选器。本文大部分内容摘自微软官网:https://learn.microsoft.com/zh-cn/aspnet/core/signalr/hub-filters?view=aspnetcore-7.0废话不多说,下面我们直接进入本章主题。中心筛选器:在ASP.NETCore5.0或更高版本中可用。允许......