【题解】Tree Purfer+DP+组合数学 —Qiuly

其实这道题叫 $a$ …. 但是总不能直接贴 $a$ 吧 $QwQ$ ，所以干脆叫 $Tree$ 好了。

~~我不会告诉你们我组合数打反了导致本来 A 的爆 0 了 TAT~~

听说 $DP$ 不是正解，不过， $DP$ 复杂度高达 $O(n^4)$ ，听说本应该 $T$ 的，却仗着小常数不仅 $AC$ ，还爆踩标程？~~这究竟是道德的沦丧还是人性的扭曲？~~

不了不了，正经一点。众所周知，有个东西叫 $Purfer$ 序列，对于每一个不同的树，都有不同的 $Purfer$ 序列。所以每个树都可以用其 $Purfer$ 序列来表示，这个树中的每个结点在 $Purfer$ 序列中的出现次数为其度数减一。至于 $Purfer$ 序列具体是什么就不赘述了。

那么 $DP$ 方程怎么设？

我们设 $f[i][j][k]$ 表示 从前 $i$ 个结点中选出 $j$ 个结点，并且这 $j$ 个结点共在原树的 $Purfer$ 序列出现了 $k$ 次的合法 $Purfer$ 序列的数量 。

那么转移呢？很显然分为两种情况：

没选第 $i$ 个点。
选了第 $i$ 个点。

然后分别进行转移，这就很简单了：

没选： $f[i][j][k]+=f[i-1][j][k]$
选了： $f[i][j][k]+=f[i-1][j-1][k-d]\times C[k][d]$

其中 $d$ 为我们正在枚举的第 $i$ 个点的出现次数 $(0$ ~ $du[i]-1)$ ，然后就是下面的组合数，就是代表着在 $k-d$ 长度的序列中插入 $d$ 个 $i$ 的方案数 。
当然也可以这么写：

$f[i][j+1][d+k]+=C[d+k][d]\times f[i-1][j][k]$
我们知道一棵

$n$ 个结点的树的

$Purfer$ 序列的长度是

$n-2$ 的，所以我们的答案应该就是

$f[n][i][i-2]$ 。

最后，记得随时膜模！

Code:

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=57;
const int MOD=1000000007;
int du[N],n,T;
ll C[N][N],f[N][N][N];
int main() {
    C[0][0]=1;
    for(int i=1;i<=50;++i){
        C[i][0]=C[i][i]=1;
        for(int j=1;j<i;++j)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
    }
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;++i)
            scanf("%d",&du[i]);
        memset(f,0,sizeof(f));
        f[0][0][0]=1;
        for(int i=1;i<=n;++i)
            for(int j=0;j<i;++j)
                for(int k=0;k<=n-2;++k) {
                    f[i][j][k]=(f[i][j][k]+f[i-1][j][k])%MOD;
                    for(int d=0;d<du[i]&&d+k<=n-2;++d)
                        f[i][j+1][d+k]=(f[i][j+1][d+k]+C[d+k][d]*f[i-1][j][k]%MOD)%MOD;
                }
        printf("%d ",n);
        for(int i=2;i<=n;++i)printf("%lld ",f[n][i][i-2]);
        printf("\n");
    }
    return 0;
}

【题解】Tree Purfer+DP+组合数学 —Qiuly

于2019年3月27日2019年3月27日由Qiuly发布

Qiuly

3 条评论

litble · 2019年3月27日 6:49 下午

Remmina · 2019年3月27日 4:09 下午

Qiuly · 2019年3月27日 4:34 下午

发表回复取消回复

【题解】Tree Purfer+DP+组合数学 —Qiuly

于2019年3月27日2019年3月27日由Qiuly发布

Qiuly

3 条评论

litble · 2019年3月27日 6:49 下午

Remmina · 2019年3月27日 4:09 下午

Qiuly · 2019年3月27日 4:34 下午

发表回复 取消回复

发表回复取消回复