首页 > 代码库 > UVa 1645 Count(**)
UVa 1645 Count(**)
题目大意:输入n,统计有多少个n个结点的有根树,使得每个深度中所有结点的子结点数相同。结果模1000000007。
思路:根据题意,每个结点的每个子树都是相同的。所以n结果为n-1的所有约数的结果加起来。
示意图:
代码如下:
1 #include <iostream> 2 #include <sstream> 3 #include <cstdio> 4 #include <cstring> 5 #include <cmath> 6 #include <string> 7 #include <vector> 8 #include <set> 9 #include <cctype>10 #include <algorithm>11 #include <cmath>12 #include <deque>13 #include <queue>14 #include <map>15 #include <stack>16 #include <list>17 #include <iomanip>18 19 using namespace std;20 21 #define INF 0x7fffffff22 #define maxn 101023 typedef long long ll;24 const int MOD = 1000000007;25 26 ll ans[maxn];27 28 void init()29 {30 memset(ans, 0, sizeof(ans));31 ans[1] = 1;32 for(int i = 2; i < maxn; i++)33 {34 for(int j = 1; j < i; j++)35 {36 if((i-1)%j) continue;37 ans[i] += ans[j];38 ans[i] %= MOD;39 }40 }41 }42 43 int main()44 {45 init();46 int n, kase = 0;47 while(cin >> n)48 {49 cout << "Case " << ++kase << ": "<< ans[n] << endl;50 }51 return 0;52 }
UVa 1645 Count(**)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。