Liveddd's Blog

愛にできることはまだあるかい

LOJ#3980. 「NOI2023」桂花树

发表于 更新于 分类于
本文字数： 2.8k 阅读时长 ≈ 6 分钟

好的 DP 题，但是感觉手玩几下就出来了。

先只考虑第一个限制。手玩一下得到，原树的结构是不变。需要考虑，在原树上的一条边插入一个新节点，或者在一个节点下方加一个新节点。

考虑 $k=0$ 的情况，从小到大考虑，那么与上面一样只有两种操作。每次插入有 $2n-1$ 种选择，插入后变为 $n+1$ 的情况。以此类推得到答案 $\displaystyle\prod_{i=n}^{n+m-1}(2i-1)$。期望得分 $\text{35 pts}$（实测有 $\text{50 pts}$）。

考虑 $k\le 10$ 的情况。第二个限制相当于对于 $[1,i]$ 的所有节点所构成的虚树属于 $[1,i+k]$。依然从小到大考虑，不同于 $k=0$ 的两种操作，我们可以进行这样一种操作：在一条边上插入一个新节点 $x$，在 $x$ 节点下方插入一个新节点 $y$，满足 $y<x\le y+k$。而对于当前状态，我们先填上 $y$，再状压记录空白节点 $x$ 的上限 $y+k$，之后填上 $x$。

于是设计状态 $f(i,S)$ 表示填到 $i$，未填的节点的上限状态为 $S$ 的方案数。那么有几种转移，其中 $size=n+\text{popcount}(S)$：

  1. 在一条边插入一个新节点 $i$，系数为 $size-1$。
  2. 在一个节点下方加一个新节点 $i$，系数为 $size$。
  3. 在一条边插入一个空白节点，将 $i$ 加在空白节点下方。
  4. 在一个空白节点上填上 $i$。

时间复杂度 $\mathcal O(Tmk2^k)$。答案与原树的形态无关。

感觉挺平凡的，但是又比较巧妙。

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<iostream>
#include<cstdio>
#include<cstring>
#define lowbit(x) (x&(-x))
using namespace std;
const int N=10,M=1<<N,mod=1e9+7;
template<class T>
inline void read(T &x)
{
    x=0;int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int type,T,n,m,k,tot;
int f[M],g[M];
int cnt[M];
inline int adj(int x){return x>=mod?x-mod:x;}
inline void upd(int &x,int y){x+=y,x=x>=mod?x-mod:x;}
inline void solve()
{
    read(n,m,k);
    for(int i=2,fa;i<=n;i++)read(fa);
    if(k==0)
    {
        int res=1;
        for(int i=n;i<n+m;i++)res=1ll*res*(2*i-1)%mod;
        printf("%d\n",res);
        return ;
    }
    tot=1<<k;
    int high=tot>>1;
    memset(f,0,sizeof(f));
    f[0]=1;
    for(int i=n;i<n+m;i++)
    {
        for(int j=high;j<tot;j++)g[(j^high)<<1]=f[j];
        for(int j=0;j<high;j++)
        {
            for(int t=j;t;)
            {
                int now=lowbit(t);
                upd(g[(j^now)<<1],f[j]);
                t^=now;
            }
            int si=i+cnt[j];
            upd(g[j<<1|1],1ll*(si-1)*f[j]%mod);
            upd(g[j<<1],1ll*(2*si-1)*f[j]%mod);
        }
        memcpy(f,g,sizeof(f));
        memset(g,0,sizeof(g));
    }
    printf("%d\n",f[0]);
}
int main()
{
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    read(type,T);
    for(int i=0;i<(M>>1);i++)cnt[i<<1]=cnt[i],cnt[i<<1|1]=cnt[i]+1;
    while(T--)solve();
    return 0;
}