[NOI2023] 桂花树
题目描述
小 B 八年前看到的桂花树是一棵 \(n\) 个节点的树 \(T\),保证 \(T\) 的非根结点的父亲的编号小于自己。给定整数 \(k\),称一棵 \((n+m)\) 个节点的有根树 \(T^{\prime}\) 是繁荣的,当且仅当以下所有条件满足:
- 对于任意满足 \(1 \le i,j \le n\) 的 \((i,j)\),在树 \(T\) 和树 \(T^{\prime}\) 上,节点 \(i\) 和 \(j\) 的最近公共祖先编号相同。
- 对于任意满足 \(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]);
}
}
标签:10,le,编号,样例,测试数据,NOI2023,桂花树,节点
From: https://www.cnblogs.com/mekoszc/p/17914113.html