首页 > 其他分享 >[NOI2023] 桂花树

[NOI2023] 桂花树

时间:2023-12-19 16:48:16浏览次数:26  
标签:10 le 编号 样例 测试数据 NOI2023 桂花树 节点

[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]);
	}
}

标签:10,le,编号,样例,测试数据,NOI2023,桂花树,节点
From: https://www.cnblogs.com/mekoszc/p/17914113.html

相关文章

  • [NOI2023] 贸易
    题意:给定一棵深度为\(n\)的完美二叉树,根节点为\(1\),对于所有非\(1\)的点,都有一条连到其父亲的边权为\(a_i\)的单向边,除此之外,还给定了\(m\)条单向边(\(u\rightarrowv)\),边权为\(w\),保证\(u\)是\(v\)的祖先,求\(\sum_{i=1}^{2^n-1}\sum_{j=1}^{2^n-1}dis(i,j)\),其......
  • NOI2023 D1T2 桂花树
    称编号\(>n\)的点为新点。由条件1可以推出树\(T\)为结点\(1\simn\)在树\(T'\)上的虚树。由条件2可以推出\(\forall1\leu<v\len+m,\operatorname{lca}(u,v)\lev+k\)。首先考虑\(k=0\)的做法:此时\(\forall1\leu<v\len+m,\operat......
  • noi2023游记
    前情提要tjD类什么垃圾不用我说了吧。Day-1到场了,挺热的。和两位同校巨佬分到了一个宿舍还有一位E类都比我强/kel中午和三位同校巨佬还有教练去外面吃了一顿火锅,选的微辣但是我还是有点接受不了。北方人没吃过油碟。没有麻酱我们都有点奇怪。幸亏有冰红茶解辣。成......
  • NOI2023 D2T1 贸易
    图中不存在横插边,\(u\rightsquigarrowv\)可拆成\(u\rightsquigarrow\operatorname{lca}(u,v)\rightsquigarrowv\)计算。对\(u\rightsquigarrow\operatorname{lca}(u,v)\),不可能走第二类道路,树形DP统计每条边被经过的次数并累加答案即可,时间复杂度\(\mathcalO(2......
  • NOI2023Day2T2
    \(36pts\)\(O(tqn^2)\)暴力即可\(40pts\)对于最朴素的暴力优化,从头到尾扫,如果已经当前位字符比出优先级,那么直接能判断了,没必要往后跑了,第15个性质B的也给跑过了,我没料到,不过数据强一点其实和20pts没区别\(性质A(60pts)\)没有想出来\(性质B(72pts)\)写这个性质只有12pts,但......
  • 【NOI2023】合并书本
    Description传送门SolutionPart1考虑一棵合并树,令\(ls_u,rs_u\)表示\(u\)的左右儿子,\(d_u\)表示\(u\)子树的最大深度,\(c_u\)表示\(u\)被合并的次数,令所有非叶非根节点对应\(2^d-1\)的和为\(S\),则答案为\(\sum_{i=1}^nc_iw_i+S\)。可以发现,我们只关心\(c......
  • lg9483 [NOI2023] 合并书本
    考虑对合并过程建一棵树。对于一个点\(x\),定义\(a_x\)表示它向上合并的时候,对答案造成的重量贡献的系数。定义一个点的层级\(d_x\)为它的两个儿子层级的较大值\(+1\)。我们称\(d\)更小的层级为更深的层级。那么层级为\(i\)的非根非叶子节点会对答案造成\(2^i-1\)的......
  • NOI2023 打金记
    扔到cnblogs上。##Day-4最后一场模拟赛,肯定要用力打啊!然而一题不会,呜呜呜。于是开始拼暴力,写了$90+60+60=210$,结果挂成$40+60+60=160$。T1我将题目转化为:对于一个排列,每次只改动三个位置,要求某个数的出现位置,我用了fhq-treap!维护一个桶就好了,不知道自己......
  • NOI2023 题解
    打的太shaber了,于是补补题。D1T1扫描线。首先我们可以容斥一下,答案为被一种操作覆盖到的减去被两种操作覆盖到的加上被三种操作覆盖到的。首先考虑只被一种操作覆盖到的,这很简单,直接上个区间颜色段推平就好了,顺便去了个重。接下来是有被斜线覆盖到的,这样的点数为\(O(nk)\)......
  • P9481 [NOI2023] 贸易 题解
    题目链接题目要求我们求出任意两点间最短路径之和,由于图比较特殊,除树边外只有祖先到其子树内的边,我们首先考虑最短路径有没有什么特殊性质。注意到两点之间的最短路分为一下三种:节点到其祖先的最短路:直接沿着树边向上走即可,否则一定会走多余的边,不是最优。节点到其子树的......