图论:Prufer编码
2024-08-26 10:35:38
BZOJ1211:使用prufer编码解决限定结点度数的树的计数问题
首先学习一下prufer编码是干什么用的
prufer编码可以与无根树形成一一对应的关系
一种无根树就对应了一种prufer编码
先介绍编码过程:
选择无根树中度数为1的最小编号节点(也就是编号最小的叶子节点),将其删除,把它的邻接点加入数组
不断执行上述操作直到树中仅剩两个节点
解码过程:
顺序扫描prufer编码数组,将扫到的第一个节点记为节点u,寻找不在prufer编码中的没有被标记的最小编号的节点v
连接u-v并把v标记,将u从prufer编码数组删除并扫描下一个节点
性质:
一个点的入度为d,那么它最多有可能在prufer编码中出现d-1次
prufer编码一共有n-2个数字,每个相同的数字出现d-1次
针对这道题,如果我们给出了每个点的度数要求,那么满足要求的树的个数就是可生成的不同的prufer编码的个数:
(n - ) ! / ( (d1 - )! (d2 - )! ……(dn - )! )
这样就是答案了
下面介绍题目的实现方法(这个题比较简单,只是借助了prufer编码的性质进行计数,不涉及编码和解码的过程)
const int maxn=;
int n,tot,cnt;
int pri[maxn],d[maxn],num[maxn];
long long ans=;
long long s[];
tot用来统计prufer编码中应有的节点数,看是否满足等于n-2
cnt用来计数素数的个数,便于分解质因数
pri里存的的是每一个质数,num里存的是质数出现的次数
s用来预处理阶乘
抛开这道题,我们重点应该学一学这个分解质因数的方法
void solve(long long x,int f) //按照指数分解质因数
{
for(int i=;i<=cnt;i++)
{
if(x<=) return;
while(x%pri[i]==) {num[i]+=f;x/=pri[i];}
}
}
满足题目的需求,直接计数即可:
solve(s[n-],); //计算阶乘并将结果分解质因数
for(int i=;i<=n;i++) solve(s[d[i]],-); //同上
for(int i=;i<=cnt;i++)
while(num[i]--) ans*=pri[i]; //统计结果
printf("%lld",ans);
下面给完整的代码:
#include<cmath>
#include<cstdio>
const int maxn=;
int n,tot,cnt;
int pri[maxn],d[maxn],num[maxn];
long long ans=;
long long s[];
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>'') {if(ch=='-')f=-; ch=getchar();}
while(ch>=''&&ch<='') {x*=;x+=ch-'';ch=getchar();}
return x*f;
}
bool jud(int x)
{
for(int i=;i<=sqrt(x);i++)
if(x%i==) return ;
return ;
}
void getpri()
{
for(int i=;i<=;i++)
if(jud(i)) pri[++cnt]=i;
}
void solve(long long x,int f) //按照指数分解质因数
{
for(int i=;i<=cnt;i++)
{
if(x<=) return;
while(x%pri[i]==) {num[i]+=f;x/=pri[i];}
}
}
int main()
{
s[]=;
for(int i=;i<=;i++) s[i]=s[i-]*i;
getpri();
n=read();
if(n==)
{
int x=read();
if(x==) printf("");
else printf("");
return ;
}
for(int i=;i<=n;i++)
{
d[i]=read();
if(d[i]==) {printf("");return ;}
d[i]--;
tot+=d[i];
}
if(tot!=n-) {printf(""); return ;}
solve(s[n-],); //计算阶乘并将结果分解质因数
for(int i=;i<=n;i++) solve(s[d[i]],-); //同上
for(int i=;i<=cnt;i++)
while(num[i]--) ans*=pri[i]; //统计结果
printf("%lld",ans);
return ;
}
最新文章
- Matlab 绘制三维立体图(以地质异常体为例)
- Spring, MyBatis 多数据源的配置和管理
- dos学习
- linux 安装rz sz命令
- CI控制器中设置在其它方法中可用的变量
- Node.js高级编程读书笔记Outline
- 关于Eclipse插件开发-----加入首选项(preferencePages)
- ruby oop学习
- Calculation(dfs+状压dp)
- phpStudy速度慢的解决办法
- Android中adb push和adb install的使用区别
- Python错误集
- Java的类加载器
- 笔记:I/O流-ZIP文档
- 使用 JS 嵌入的方式来加载 Flash 插件,在各浏览器中播放视频
- Hadoop2.7.6_03_HDFS原理
- linux:Apache服务器相关
- UVa 442 Matrix Chain Multiplication(栈的应用)
- [转]详解C#组件开发的来龙去脉
- iOS开发-常用第三方开源框架介绍(你了解的ios只是冰山一角)--(转)