简答题 偏难
#7225

技能树 设二叉树中每个节点的子节点数为0或2,求有N个节点高度为M的不同的二叉树有多少个 (输出 mod 9901 后的结果)。 时间限制:10000 内存限制…

技能树

设二叉树中每个节点的子节点数为0或2,求有N个节点高度为M的不同的二叉树有多少个

(输出 mod 9901 后的结果)。

时间限制:10000

内存限制:131072

输入

两个空格分开的整数, N和K。

输出

第 1 行: 一个整数,表示可能的技能树的个数除以9901的余数。

样例输入

5 3

样例输出

2

提示

有5个节点,高为3的两个不同的技能树。约定:n在[3,300]间,m在(1,100)间

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;cstdio&gt; #include &lt;cstdlib&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; using namespace std; #define N 310 #define M 110 #define mod 9901 int f[M][N], sum[N][M]; int main() {   int n, m;   scanf("%d%d", &amp;n, &amp;m);   f[1][1] = sum[1][1] = 1;   for (int j = 2; j &lt;= n; j++)     f[1][j] = sum[1][j] = 0;   for (int i = 2; i &lt;= m; i++) {     for (int j = 1; j &lt;= n; j++) {       f[i][j] = 0;       for (int k = 1; k &lt; j; k++)         f[i][j] = (f[i][j] + (2 * f[i - 1][k] * sum[i - 1][j - k - 1] -                               f[i - 1][k] * f[i - 1][j - k - 1]) %                                  mod) %                   mod;       sum[i][j] = (sum[i - 1][j] + f[i][j]) % mod;     }   }   printf("%d\n", f[m][n]);   return 0; }</pre>
这道题暂未补解析。