[***]HZOJ 超级树

DeepinC超详细题解

考试时想出是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了。还是要注意细节啊。

 #include<iostream>

 #include<cstdio>

 #define LL long long

 using namespace std;

 LL n,mod;

 LL f[][];

 signed main()

 {

     cin>>n>>mod;

     f[][]=f[][]=;

     for(int i=;i<n;i++)

     {

         for(int j=;j<=n-i+;j++)

         {

             for(int k=;k<=n-i-j+;k++)

             {

                 LL num=f[i][j]*f[i][k]%mod;

                 f[i+][k+j]     =( f[i+][k+j]   +num         )%mod;

                 f[i+][k+j]  =( f[i+][k+j]   +*num*(j+k) )%mod;

                 f[i+][k+j+]=( f[i+][k+j+] +num         )%mod;

                 f[i+][k+j-]=( f[i+][k+j-] +*num*j*k   )%mod;

                 f[i+][k+j-]=( f[i+][k+j-] +num*j*(j-) )%mod;

                 f[i+][k+j-]=( f[i+][k+j-] +num*k*(k-) )%mod;

             }

         }

     }

     printf("%lld\n",f[n][]%mod);

 }

巴特西

[***]HZOJ 超级树

最新文章

热门文章