博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
HDU-4472 Count 递推
阅读量:4622 次
发布时间:2019-06-09

本文共 928 字,大约阅读时间需要 3 分钟。

题意:有N个节点的图,现在要求构成一棵树(不存在环),且只能够有一个跟节点,每一层的节点数还必须相同。问有多少种不同的方式。

解法:对于N个节点而言,如果第N个节点是N-1个节点任意一种组合情况下的boss的boss,这种事满足情况的,用f[N]表示方案数的话,那么这部分的值就是f[N-1];如果N不属于上面的情况,那么可以认为N个节点的组合下,boss下面就直接分成了一个个支,由于各层节点数要相等,因此每个分支的情况都要一样,所以N-1有多少个大于2的因子就有多少种情况了。

综上:如果把f[x-1]看作一个分支的话,有:

代码如下:

#include 
#include
#include
#include
#include
using namespace std;const int MOD = int(1e9)+7;int f[1005];void pre() { f[1] = f[2] = 1; for (int i = 3; i <= 1000; ++i) { for (int j = 1; j <= i-1; ++j) { if ((i-1) % j == 0) { f[i] += f[(i-1)/j]; f[i] %= MOD; } } }}int main() { pre(); int ca = 0, N; while (scanf("%d", &N) != EOF) { printf("Case %d: %d\n", ++ca, f[N]); } return 0; }

 

 

转载于:https://www.cnblogs.com/Lyush/archive/2013/04/25/3042404.html

你可能感兴趣的文章
php写一个判断是否有cookie的脚本
查看>>
Mac配置Fiddler抓包工具
查看>>
转:Java并发集合
查看>>
Word截图PNG,并压缩图片大小
查看>>
Python项目对接CAS方案
查看>>
mysql产生随机数
查看>>
编程风格
查看>>
熟悉常用的Linux命令
查看>>
易之 - 我是个大师(2014年3月6日)
查看>>
Delphi中窗体的事件
查看>>
file_get_contents()获取https出现这个错误Unable to find the wrapper “https” – did
查看>>
linux vi编辑器
查看>>
js树形结构-----(BST)二叉树增删查
查看>>
contract
查看>>
Python语言编程
查看>>
[poj 1469]Courses
查看>>
vue+element-ui实现表格checkbox单选
查看>>
测试开发学习进阶教程 视频&PDF
查看>>
C#基础-连接Access与SQL Server
查看>>
autofac
查看>>