首页 > 代码库 > UVA - 1645 - Count(思路)
UVA - 1645 - Count(思路)
题意:输入n(1 <= n <= 1000),输出有n个结点且每个深度中所有结点的子节点数相同的树有多少种。
根据题意,其实要求每个子树都相同。
一个结点当作根节点,还剩下n - 1个结点,枚举n - 1的因子(因子当作紧邻根结点的子树中的结点数),然后将所有因子的答案相加即可。
代码如下:
#include<cstdio> #include<cstring> #include<cctype> #include<cstdlib> #include<cmath> #include<iostream> #include<sstream> #include<iterator> #include<algorithm> #include<string> #include<vector> #include<set> #include<map> #include<deque> #include<queue> #include<stack> #include<list> #define fin freopen("in.txt", "r", stdin) #define fout freopen("out.txt", "w", stdout) #define pr(x) cout << #x << " : " << x << " " #define prln(x) cout << #x << " : " << x << endl #define Min(a, b) a < b ? a : b #define Max(a, b) a < b ? b : a typedef long long ll; typedef unsigned long long llu; const int INT_INF = 0x3f3f3f3f; const int INT_M_INF = 0x7f7f7f7f; const ll LL_INF = 0x3f3f3f3f3f3f3f3f; const ll LL_M_INF = 0x7f7f7f7f7f7f7f7f; const double pi = acos(-1.0); const double EPS = 1e-6; const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1}; const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1}; const ll MOD = 1e9 + 7; using namespace std; #define NDEBUG #include<cassert> const int MAXN = 1000 + 10; const int MAXT = 10000 + 10; ll c[MAXN]; void init(){ c[0] = 0ll; c[1] = 1ll; c[2] = 1ll; for(int i = 3; i < MAXN; ++i){ int t = i - 1; c[i] = 0ll; for(int j = 1; j <= t; ++j) if(t % j == 0) (c[i] += c[j]) %= MOD; } } int main(){ init(); int kase = 0, n; while(scanf("%d", &n) == 1) printf("Case %d: %lld\n", ++kase, c[n]); return 0; }
UVA - 1645 - Count(思路)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。