考试时想出是dp了，因为显然第i级超级树和第i+1级超级树是有联系的（然而我并不能推出来），这dp的状态鬼才想的出来……个人理解，dp的实质就是从小的状态向大的状态转移，从而得到最终答案，状态分的越细，转移起来就越容易理解，同时相应的时间和空间复杂度也会变大。dp数组的设置就相当于分配状态，那么一开始为什么不把它分的细一点呢？最后在考虑优化。

回到这个题，设f[i][j]为第i级超级树，其中有j条路径且这些路径没有相同的点的方案数（有点难以理解，但这样是为了保证没有重复过某点），边界f[1][1]=f[1][0]=1;

这题主要的难点就是状态的设置，然后就是转移有点多，很容易忘掉其中几个，想明白后其他的就比较简单了。

考虑dp[i]对dp[i+1]的

贡献:枚举左子树和右子树的路径条数l、r,记num=dp[i][l]*dp[i][r],则有

• 什么也不做 dp[i+1][l+r]+=num

• 根自己作为一条新路径 dp[i+1][l+r+1]+=num

• 根连接到左子树(或右子树)的某条路径上 dp[i+1][l+r]+=2*num*(l+r)

• 根连接左子树和右子树的各一条路径 dp[i+1][l+r-1]+=2*num*l*r

• 根连接左子树(或右子树)的两条路径 dp[i+1][l+r-1]+=num*(l*(l-1)+r*(r-1))

最后答案即为f[n][1]，n级超级树，有1条路径的方案数，实际上就是有几条路径。

然后还有两个坑点：

1.如果$n^3$枚举会T，我不知道知道为啥，所以要考虑优化，DeepinC给了三条优化方案，这里只选去一条：能给f[i][j]贡献答案的，是f[i-1][?]，问号如果是大于i+1，显然就没用了。即两维之和不超过n+i所以为了求出f[n][1],那么两维之和就不必超过n+1。所以对j的限制就是0～（n-i+2）那么对k的限制就更紧了，0～（n-i+2-j）。

2.试试这个点 1 1。如果最后输出时不取模的话会输出1，然后就WA了。还是要注意细节啊。

1 #include
      
        2 #include
       
         3 #define LL long long 4 using namespace std; 5 LL n,mod; 6 LL f[310][400]; 7 signed main() 8 { 9     cin>>n>>mod;10     f[1][0]=f[1][1]=1;11     for(int i=1;i