[海军国际项目办公室]数树

2024-03-16 22:38

本文主要是介绍[海军国际项目办公室]数树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

数树

题目概述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

题解

我们先不考虑树 T 2 T2 T2树内部的同构情况,算出总的方案数,最后除去同构的方案。
显然,树 T 1 T1 T1 T 2 T2 T2都是无根树,我们不妨先给 T 1 T1 T1定一个根,这样的话, T 1 T1 T1中每一种能映射到 T 2 T2 T2上的合法方案都会存在一个确定的根,在我们将我们把 T 2 T2 T2的根定义为该对应点时,这两块刚好能够匹配。
我们不妨枚举在 T 2 T2 T2中每个点为根时的情况,这样所有点的相对高度与位置都是确定的,我们可以把它放到 T 1 T1 T1上,看有多少个连通块能跟其匹配。

T 2 T2 T2放到 T 1 T1 T1求出匹配显然可以用 d p dp dp来求出。
我们定义 d p i , j dp_{i,j} dpi,j表示 T 1 T1 T1上的点 i i i匹配 T 2 T2 T2上的点 j j j的方案数。
其转移过程我们可以通过状压来维护。
由于我们此时 T 2 T2 T2的根是固定的,所以点 j j j T 2 T2 T2上的儿子也是固定的。
我们要让 i i i T 1 T1 T1上的儿子依次匹配 j j j T 2 T2 T2上的儿子,求出匹配的方案数。
我们定义 f i , j , S f_{i,j,S} fi,j,S表示 i i i T 1 T1 T1上的儿子匹配了 j j j T 2 T2 T2上的儿子集合为 S S S的方案数,其转移显然是一个背包的过程,加入的 i i i的儿子,枚举其匹配 j j j的哪一个儿子或者不匹配。
显然, d p i , j = f i , j , s o n j dp_{i,j}=f_{i,j,son_{j}} dpi,j=fi,j,sonj,其中 s o n j son_{j} sonj表示 j j j儿子的全集。
∑ i = 1 n d p i , r t \sum_{i=1}^{n}dp_{i,rt} i=1ndpi,rt就是 T 2 T2 T2 r t rt rt为根放到 T 1 T1 T1上匹配得到的方案数之和。
我们要枚举 r t rt rt,整个 d p dp dp的过程是 O ( n m 2 2 m ) O\left(nm^22^m\right) O(nm22m)的。

但是 T 2 T2 T2的内部存在同构的情况,比如一棵完全二叉树,交换它的左右儿子,树的形态并没有发生改变,但如果是我们上面的匹配过程的话,它是会被重复计算的。
即相同的点集,存在不同的映射方法,而这种映射方法会导致我们的重复计算。
而这种映射方法在匹配的根不同的情况下依旧可能导致相同,如果只根据匹配方的点集是相当麻烦的。
我们不如考虑以某一个点为根的树形态会产生多少的同构,也就是按以这个节点为根的树与我们的原 T 2 T2 T2进行上面 d p dp dp转移的匹配,得到的 h r t h_{rt} hrt表示以 r t rt rt为根的 T 2 T2 T2与原 T 2 T2 T2的同构数。
将原来的 ∑ i = 1 n d p i , r t \sum_{i=1}^{n}dp_{i,rt} i=1ndpi,rt除去 h r t h_{rt} hrt即可,因为原来匹配的就是以 r t rt rt为根的树,它产生的同构树与 h r t h_{rt} hrt相当。
所以这样跑两趟 d p dp dp就可以了。

时间复杂度 O ( ( n + m ) m 2 2 m ) O\left((n+m)m^22^m\right) O((n+m)m22m)

源码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 3005
#define MAXM (1<<10)+5
#define lowbit(x) (x&-x)
#define reg register
#define pb push_back
#define mkpr make_pair
#define fir first
#define sec second
#define debug(x) cerr<<#x<<"="<<x<<'\n'
typedef long long LL;
typedef unsigned long long uLL;     
const LL INF=0x3f3f3f3f3f3f3f3f;  
const int mo=998244353;
const int inv2=499122177;
const int jzm=2333;
const int n1=50;
const int zero=10000;
const int orG=3,invG=332748118;
const double Pi=acos(-1.0);
const double eps=1e-5;
typedef pair<LL,int> pii;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=getchar();while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;
}
template<typename _T>
void print(_T x){putchar('\n');while(x>9){putchar((x%10)|'0');x/=10;}putchar(x|'0');}
LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
int add(int x,int y,int p){return x+y<p?x+y:x+y-p;}
void Add(int &x,int y,int p){x=add(x,y,p);}
int qkpow(int a,int s,int p){int t=1;while(s){if(s&1LL)t=1ll*a*t%p;a=1ll*a*a%p;s>>=1LL;}return t;}
int n,m,dp[MAXN][12],f[MAXM],tmp[MAXM],g[12][12],ans,ord[15],h[12],sumtr;
vector<int>A[MAXN],B[15],G[15];
void dosaka1(int u,int fa){G[u].clear();int siz=B[u].size();for(int i=0;i<siz;i++){int v=B[u][i];if(v==fa)continue;dosaka1(v,u);G[u].pb(v);}
}
void dosaka2(int u,int fa){int siz=A[u].size();for(int i=0;i<siz;i++)if(A[u][i]!=fa)dosaka2(A[u][i],u);for(int i=1;i<=m;i++){f[0]=1;int sz=G[i].size();for(int j=0;j<sz;j++)ord[j]=G[i][j];if(sz)for(int j=0;j<siz;j++){int v=A[u][j];if(v==fa)continue;for(int S=0;S<(1<<sz);S++)tmp[S]=f[S];for(int k=0;k<sz;k++)for(int S=0;S<(1<<sz);S++)if(!(S&(1<<k)))Add(tmp[S|(1<<k)],1ll*dp[v][ord[k]]*f[S]%mo,mo);for(int S=0;S<(1<<sz);S++)f[S]=tmp[S],tmp[S]=0;}dp[u][i]=f[(1<<sz)-1];for(int S=0;S<(1<<sz);S++)f[S]=0;}
}
void dosaka3(int u,int fa){int siz=B[u].size();for(int i=0;i<siz;i++)if(B[u][i]!=fa)dosaka3(B[u][i],u);for(int i=1;i<=m;i++){f[0]=1;int sz=G[i].size();for(int j=0;j<sz;j++)ord[j]=G[i][j];if(sz)for(int j=0;j<siz;j++){int v=B[u][j];if(v==fa)continue;for(int S=0;S<(1<<sz);S++)tmp[S]=f[S];for(int k=0;k<sz;k++)for(int S=0;S<(1<<sz);S++)if(!(S&(1<<k)))Add(tmp[S|(1<<k)],1ll*g[v][ord[k]]*f[S]%mo,mo);for(int S=0;S<(1<<sz);S++)f[S]=tmp[S],tmp[S]=0;}g[u][i]=f[(1<<sz)-1];for(int S=0;S<(1<<sz);S++)f[S]=0;}
}
signed main(){freopen("count.in","r",stdin);freopen("count.out","w",stdout);read(n);for(int i=1;i<n;i++){int u,v;read(u);read(v);A[u].pb(v);A[v].pb(u);}read(m);for(int i=1;i<m;i++){int u,v;read(u);read(v);B[u].pb(v);B[v].pb(u);}for(int rt=1;rt<=m;rt++){dosaka1(rt,0);for(int j=1;j<=m;j++)dosaka3(j,0),Add(h[j],g[j][rt],mo);	}for(int rt=1;rt<=m;rt++){dosaka1(rt,0);dosaka2(1,0);int summ=0;for(int i=1;i<=n;i++)Add(summ,dp[i][rt],mo);Add(ans,1ll*summ%mo*qkpow(h[rt],mo-2,mo)%mo,mo);}printf("%d\n",ans);return 0;
}

谢谢!!!

这篇关于[海军国际项目办公室]数树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/816951

相关文章

一文教你如何将maven项目转成web项目

《一文教你如何将maven项目转成web项目》在软件开发过程中,有时我们需要将一个普通的Maven项目转换为Web项目,以便能够部署到Web容器中运行,本文将详细介绍如何通过简单的步骤完成这一转换过程... 目录准备工作步骤一:修改​​pom.XML​​1.1 添加​​packaging​​标签1.2 添加

tomcat多实例部署的项目实践

《tomcat多实例部署的项目实践》Tomcat多实例是指在一台设备上运行多个Tomcat服务,这些Tomcat相互独立,本文主要介绍了tomcat多实例部署的项目实践,具有一定的参考价值,感兴趣的可... 目录1.创建项目目录,测试文China编程件2js.创建实例的安装目录3.准备实例的配置文件4.编辑实例的

springboot集成Deepseek4j的项目实践

《springboot集成Deepseek4j的项目实践》本文主要介绍了springboot集成Deepseek4j的项目实践,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价... 目录Deepseek4j快速开始Maven 依js赖基础配置基础使用示例1. 流式返回示例2. 进阶

SpringBoot项目启动报错"找不到或无法加载主类"的解决方法

《SpringBoot项目启动报错找不到或无法加载主类的解决方法》在使用IntelliJIDEA开发基于SpringBoot框架的Java程序时,可能会出现找不到或无法加载主类com.example.... 目录一、问题描述二、排查过程三、解决方案一、问题描述在使用 IntelliJ IDEA 开发基于

SpringBoot项目使用MDC给日志增加唯一标识的实现步骤

《SpringBoot项目使用MDC给日志增加唯一标识的实现步骤》本文介绍了如何在SpringBoot项目中使用MDC(MappedDiagnosticContext)为日志增加唯一标识,以便于日... 目录【Java】SpringBoot项目使用MDC给日志增加唯一标识,方便日志追踪1.日志效果2.实现步

Ubuntu中Nginx虚拟主机设置的项目实践

《Ubuntu中Nginx虚拟主机设置的项目实践》通过配置虚拟主机,可以在同一台服务器上运行多个独立的网站,本文主要介绍了Ubuntu中Nginx虚拟主机设置的项目实践,具有一定的参考价值,感兴趣的可... 目录简介安装 Nginx创建虚拟主机1. 创建网站目录2. 创建默认索引文件3. 配置 Nginx4

SpringBoot项目启动错误:找不到或无法加载主类的几种解决方法

《SpringBoot项目启动错误:找不到或无法加载主类的几种解决方法》本文主要介绍了SpringBoot项目启动错误:找不到或无法加载主类的几种解决方法,具有一定的参考价值,感兴趣的可以了解一下... 目录方法1:更改IDE配置方法2:在Eclipse中清理项目方法3:使用Maven命令行在开发Sprin

Nginx实现高并发的项目实践

《Nginx实现高并发的项目实践》本文主要介绍了Nginx实现高并发的项目实践,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录使用最新稳定版本的Nginx合理配置工作进程(workers)配置工作进程连接数(worker_co

Vue项目的甘特图组件之dhtmlx-gantt使用教程和实现效果展示(推荐)

《Vue项目的甘特图组件之dhtmlx-gantt使用教程和实现效果展示(推荐)》文章介绍了如何使用dhtmlx-gantt组件来实现公司的甘特图需求,并提供了一个简单的Vue组件示例,文章还分享了一... 目录一、首先 npm 安装插件二、创建一个vue组件三、业务页面内 引用自定义组件:四、dhtmlx

SpringBoot项目注入 traceId 追踪整个请求的日志链路(过程详解)

《SpringBoot项目注入traceId追踪整个请求的日志链路(过程详解)》本文介绍了如何在单体SpringBoot项目中通过手动实现过滤器或拦截器来注入traceId,以追踪整个请求的日志链... SpringBoot项目注入 traceId 来追踪整个请求的日志链路,有了 traceId, 我们在排