526互联

[NOI2023] 桂花树

发布时间 2023-12-19 16:34:12作者: 灰鲭鲨

[NOI2023] 桂花树

题目描述

小 B 八年前看到的桂花树是一棵 \(n\) 个节点的树 \(T\)，保证 \(T\) 的非根结点的父亲的编号小于自己。给定整数 \(k\)，称一棵 \((n+m)\) 个节点的有根树 \(T^{\prime}\) 是繁荣的，当且仅当以下所有条件满足：

  1. 对于任意满足 \(1 \le i,j \le n\) 的 \((i,j)\)，在树 \(T\) 和树 \(T^{\prime}\) 上，节点 \(i\) 和 \(j\) 的最近公共祖先编号相同。
  2. 对于任意满足 \(1 \le i,j \le n + m\) 的 \((i,j)\)，在树 \(T^{\prime}\) 上，节点 \(i\) 和 \(j\) 的最近公共祖先编号不超过 \(\max(i,j)+k\)。

注意题目中所有树的节点均从 \(1\) 开始编号，且根结点编号为 \(1\)。\(T^{\prime}\) 不需要满足非根结点的父亲编号小于自己。

小 B 想知道有多少棵 \((n+m)\) 个节点的树是繁荣的，认为两棵树不同当且仅当存在某一个节点在两棵树上的父亲不同。你只输出方案数在模 \((10^9+7)\) 意义下的值。

输入格式

本题有多组测试数据。

输入的第一行包含两个整数 \(c,t\)，分别表示测试点编号和测试数据组数。\(c=0\) 表示该测试点为样例。

接下来依次输入每组测试数据，对于每组测试数据：

输入的第一行包含三个整数 \(n,m,k\)。

输入的第二行包含 \(n-1\) 个整数 \(f_2,f_3,\dots,f_n\)，其中 \(f_i\) 表示 \(T\) 中节点 \(i\) 的父亲节点编号。

输出格式

对于每组测试数据输出一行一个整数，表示繁荣的树的数量在模 \((10^9+7)\) 意义下的答案。

样例 #1

样例输入 #1

0 3
1 2 1

2 2 1
1
2 2 0
1

样例输出 #1

3
16
15

样例 #2

样例输入 #2

见附件中的 tree/tree2.in。

样例输出 #2

见附件中的 tree/tree2.ans。

样例 #3

样例输入 #3

见附件中的 tree/tree3.in。

样例输出 #3

见附件中的 tree/tree3.ans。

样例 #4

样例输入 #4

见附件中的 tree/tree4.in。

样例输出 #4

见附件中的 tree/tree4.ans。

提示

【样例解释 #1】

对于样例中的第一组测试数据，有三棵合法的树，其每个节点的的父亲构成的序列 \(\{f_2,f_3\}\) 分别为 \(\{1,1\}\)、\(\{3,1\}\)、\(\{1,2\}\)。注意这组测试数据的第二行为空行。

对于样例中的第二组、第三组测试数据，共有 \(16\) 棵树满足第一个条件，其中只有父亲序列为 \(\{4,4,1\}\) 的树在第三组测试数据中不满足第二个条件。

【样例解释 #2】

该组样例满足 \(n \le 100\)，五组测试数据中 \(m\) 分别不超过 \(0, 1, 1, 2, 2\)。

【样例解释 #3】

该组样例满足 \(k = 0\)，五组测试数据中前两组测试数据满足 \(n = 1\)，第一、三、四组测试数据满足 \(n, m \le 100\)。

【样例解释 #4】

该组样例前两组测试数据满足 \(n = 1\)，第一、三、四组测试数据满足 \(n, m \le 100\)。

【数据范围】

对于所有测试数据保证：\(1 \le t \le 15\)，\(1 \le n \le 3 \times 10^4\)，\(0 \le m \le 3000\)，\(0 \le k \le 10\)，\(1 \le f_i \le i - 1\)。

测试点编号 \(n \le\) $m \le $ $k \le $
\(1,2\) \(4\) \(4\) \(10\)
\(3\) \(3\times 10^4\) \(0\) \(10\)
\(4\) \(10^2\) \(1\) \(10\)
\(5\) \(3 \times 10^4\) \(1\) \(10\)
\(6\) \(10^2\) \(2\) \(10\)
\(7\) \(3\times 10^4\) \(2\) \(10\)
\(8,9\) \(1\) \(10^2\) \(0\)
\(10\) \(1\) \(3,000\) \(0\)
\(11\) \(1\) \(10^2\) \(10\)
\(12\) \(1\) \(3,000\) \(10\)
\(13,14\) \(10^2\) \(10^2\) \(0\)
\(15,16\) \(3\times 10^4\) \(3,000\) \(0\)
\(17,18\) \(10^2\) \(10^2\) \(10\)
\(19,20\) \(3\times 10^4\) \(3,000\) \(10\)

先概括一下题意：T2 前 \(n\) 个点的虚树是 T1，T2 前 \(i\) 个点的虚树上所有点编号不超过 \(i+k\)。

有了这个概括，就好做一点了。先考虑 \(k=0\)，那么每个点有两种插入方式，要不选一个原树上的点做父亲，要不选一个原树上的边插进去，一个个点插入，第 \(i\) 个点有 \(2(n+i-1)-1\) 种选法，乘起来就好了。

那么 \(k\) 不为0的情况呢？考虑维护 \(1\) 到 \(i\) 的虚树。那么首先它可以插入在原树的某个点的下面或者某条边上，如果现在已经插入了 \(x\) 个点，那么这就有 \(2x-1\) 种选法。同时还有可能把一条边给分岔了。这有 \(x-1\) 种选法。此时会增加两个点，枚举另外一个点。我们发现需要记录每个点是否有加过，那么 \(k\) 很小，考虑状压。记录 \(S\) 表示目前加过了哪些点，然后如果一个点已经被加过就重新算，否则按照上面的算。

复杂度 \(O(mk2^k)\)

#include<bits/stdc++.h>
using namespace std;
const int N=3005,M=1<<10,P=1e9+7;
int n,m,k,T,dp[N][M],pc[M];
int main()
{
	for(int i=1;i<M;i++)
		pc[i]=pc[i^(i&-i)]+1;
	scanf("%*d%d",&T);
	while(T--)
	{
		scanf("%d%d%d",&n,&m,&k);
		for(int i=1;i<n;i++)
			scanf("%*d");
		memset(dp,0,sizeof(dp));
		dp[1][0]=1;
		for(int i=1;i<=m;i++)
		{
			for(int j=0;j<(1<<k);j++)
			{
				if(j&1)
				{
					(dp[i+1][j>>1]+=dp[i][j])%=P;
					continue;
				}
				int c=n+i-1+pc[j];
				(dp[i+1][j>>1]+=(2*c-1LL)*dp[i][j]%P)%=P;
				for(int l=1;l<=k;l++)
					if(!(j>>l&1))
						(dp[i+1][j>>1|1<<l-1]+=(c-1LL)*dp[i][j]%P)%=P;
			}
		}
		printf("%d\n",dp[m+1][0]);
	}
}