首页 > 代码库 > 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(**)