2020牛客国庆集训派对day3 I.Rooted Tree(哈代-拉马努金拆分数列)

题目

https://ac.nowcoder.com/acm/contest/7830/I

题意

给你n个点，问你最多可以生成多少个不同构的树。这个树的深度最多为2.

题解

首先我们暴力模拟一下情况。 n = 1 时 ans = 1 n = 2 时 ans = 1 n = 3 时 ans = 2 n = 4 时 ans = 3 n = 5 时 ans = 5 n = 6 时 ans = 7 n = 7 时 ans = 11 n = 8 时 ans = 15 n = 9 时 ans = 22 n = 10 时 ans = 30 n = 11 时 ans = 42 n = 12 时 ans = 56 n = 13 时 ans = 77. 肯定有人就会问了，请问你是怎么暴力的呢？ 哈哈哈哈哈哈哈 那我说一下我手动暴力的方法把。 拿n = 8来举例。 首先需要一个点作为根节点，所以剩下的点为7个。 然后我们去分配7个点。 方法如下：

1 1 1 1 1 1 1（一个节点连接7个只有一个节点的点） 1 1 1 1 1 2（一个节点连接5个只有一个节点的点，和一个有2个节点的点） 1 1 1 1 3 1 1 1 2 2 1 1 1 4 1 1 2 3 1 2 2 2 1 1 5 1 2 4 1 3 3 2 2 3 1 6 2 5 3 4 7 （有7个节点的点） http://blog.sina.com.cn/s/blog_71942ef00102zgd7.html

好了，接下来我们得到了这样的数列： 1 1 2 3 5 7 11 15 22 30 42 56 77 … 是不是完全看不出这样的数列有什么规律呢？ 接下来科普一下哈代-拉马努金拆分数列 令T(0) = 1 T(1) = T(0) = 1; T(2) = T(1) + T(0) = 2 T(3) = T(2) + T(1) = 3 T(4) = T(3) + T(2) = 5 T(5) = T(4) + T(3)-T(0) = 7 T(6) = T(5) + T(4)-T(1) = 11 T(7) = T(6) + T(5)-T(2)-T(0)= 15 T(8) = T(7) + T(6)-T(3)-T(1)= 22 T(9) = T(8) + T(7)-T(4)-T(2)= 30 T(10) = T(9) + T(8)-T(5)-T(3)= 42

公式来源：

那我们拿到了这个公式，可是这个公式有什么规律呢？ 我们把公式减去的常数，形成一个新的数列： 1 2 5 7 12 15 22 26 35 40 既然是拆分数列，那么我们可以把这个数列拆分一下 f(x) = 1 5 12 22 35 … 和 g(x) = 2 7 15 36 40 … 先观察f(x)，我们可以发现这是个每两个数的差值是公差为3等差数列 f(x)每两个数的差值4 7 10 13 再观察g(x)，我们也可以发现这是个每两个数的差值是公差为3等差数列 g(x)每两个数的差值5 8 11 14 我们通过设一元二次方程就可以算出f(x)和g(x)的公式： f[i] = (3* i² - i) / 2; g[i] = (3* i² + i) / 2; 那么我们就可以写代码啦！

AC代码

#include <iostream> using namespace std; typedef long long ll; const ll N = 500005, mod = 998244353; ll f[N], g[N], dp[N]; int n; int main() { scanf("%d", &n); --n; for (ll i = 1; i <= n; ++i) f[i] = i * (3*i - 1) / 2; for (ll i = 1; i <= n; ++i) g[i] = i * (3*i + 1) / 2; dp[0] = 1; for (int i = 1; i <= n; ++i) { for (int j = 1; f[j] <= i; ++j) { if (j % 2==1) { dp[i] += dp[i - f[j]]; if (g[j] <= i) dp[i] += dp[i - g[j]]; } else { dp[i] -= dp[i - f[j]]; if (g[j] <= i) dp[i] -= dp[i - g[j]]; } } dp[i] %= mod; if (dp[i] < 0) dp[i] += mod; } printf("%lld\n", dp[n]); return 0; }