题解 CF830D 【Singer House】
猪脑子
2020-06-05 15:59:44
首先，对于一个n，我们思考一下如何求解这个n的路径条数，不妨设其为$f_n$。
一个思路是考虑这条路径是否经过根节点，那么有几种情况：
这条路径只包含根节点；这条路径从下面某棵子树内一条路径连上来，再连接下去
乍一看似乎能做，但是我们会发现，从一棵子树中连上来的路径可能会连回同一棵子树，那么如果我们要算$f_n$，就必须算出从深度为n-1的子树内选择两条不相交的路径的方案数$g_{n-1}$。
你可能会想继续讨论$g_n$的方案数，但是你会发现，你要算$g_n$，还得算深度为n-1的树种选三条不相交路径的方案数……
既然如此，~~我们观察一下数据范围，~~ 不妨多设一维状态：
令$f_{n,k}$代表在深度为$n$的树中选择$k$条不相交路径的方案数。
看上去似乎变难了，毕竟原题只让我们求一条路径的方案数。
但是我们发现，这个“加强”版本似乎更好做了，因为转移变得十分简单：
$$f_{n,k}=\sum_{i+j=k-1}f_{n-1,i}\times f_{n-1,j}$$
$$+\sum_{i+j=k}f_{n-1,i}\times f_{n-1,j}$$
$$+\sum_{i+j=k}f_{n-1,i}\times f_{n-1,j}\times (2k)$$
$$+\sum_{i+j=k+1}f_{n-1,i}\times f_{n-1,j}\times (k+1)\times k$$
这四种情况分别是：根节点单独形成一条链、根节点不属于任何一条链、根节点与左右子树内某条链连在一起（分从链的尾端连上来和连到链的开头两种情况）、还有根节点从某条链上连上再连到另一条链上去。
边界条件也很显然，这里就不写了。
代码如下，我写的是记忆化搜索
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int Mod=1000000007;
int f[410][410];
int F(int n,int k)
{
if(!k)return 1;
if(n==1){
return k==1;
}
if(f[n][k]!=-1)return f[n][k];
f[n][k]=0;
for(int i=0;i<=k;i++)
f[n][k]=(f[n][k]+1ll*F(n-1,i)*F(n-1,k-i))%Mod;
for(int i=0;i<k;i++)
f[n][k]=(f[n][k]+1ll*F(n-1,i)*F(n-1,k-i-1))%Mod;
for(int i=0;i<=k;i++)
f[n][k]=(f[n][k]+1ll*F(n-1,i)*F(n-1,k-i)%Mod*k*2)%Mod;
for(int i=0;i<=k+1;i++)
f[n][k]=(f[n][k]+1ll*F(n-1,i)*F(n-1,k+1-i)%Mod*(k+1)*k)%Mod;
return f[n][k];
}
int main()
{
int n;scanf("%d",&n);
memset(f,-1,sizeof(f));
printf("%d\n",F(n,1));
return 0;
}
```
~~好不容易自己搞出2800的题，而且还没有别人发题解，怎么着也得水一下啊对不对~~