其实这道题叫 $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;
}
分类: 文章

Qiuly

QAQ

3 条评论

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

一般来说不跑满的 100 都能过 $O(n^4)$,这题才 50……

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

$n = 50$,10 组数据,$50 ^ 4 \times 10 = 6.25 \times 10 ^ 7$,为啥会 TLE?

回复 Qiuly 取消回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注