首页 > 其他分享 >5034. 【NOI2017模拟3.28】B —— 矩阵树定理和拉格朗日插值的结合

5034. 【NOI2017模拟3.28】B —— 矩阵树定理和拉格朗日插值的结合

时间:2024-06-23 22:35:38浏览次数:24  
标签:拉格朗 moder int 5034 矩阵 插值 NOI2017 权值 3.28

题目大意

给你一棵 \(n\)(\(n\le50\))个点的树,可以进行不超过 \(k\) 次操作,每次断掉一条边,再连上一条边,要求树一直是树,求一共有多少种树的形态。

思路

把题意转换为对于一个 \(n\) 个点的完全图,是树边的话权值是 \(1\),否则是 \(x\)。

跑一遍矩阵树定理,矩阵树定理求的是一个图所有生成树的权值和,在这里一棵生成树的权值被定义为边权的乘积。跑出权值和以后,\(x^i\) 项的系数就是选了 \(k\) 条非树边的生成树个数。

由于操作数不超过 \(k\) 个,所以非树边的个数小于等于 \(k\),只需要把指数小于等于 \(k\) 的项的系数加起来就是答案。

但是,这样子看起来相当不好求,因此考虑拉格朗日插值。

由于最后矩阵树出来的多项式最多有 \(n-1\) 项,所以只需要把 \(x\) 从 \(1\) 到 \(n\) 代入跑 \(n\) 次矩阵树,然后拉格朗日插值还原出矩阵树的多项式。

相关知识点

矩阵树定理

(P6178 【模板】Matrix-Tree 定理 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

定义两个矩阵:度数矩阵 \(D_{i,i}=点 i 的度数\),邻接矩阵 \(A_{i,j}=(i,j)的权值\)。

求出 \(\det (D-A)\) 就是答案了。

矩阵树定理及其无向图形式证明 - 洛谷专栏 (luogu.com.cn)

求 \(\det (D-A)\) 的话,只需要选出任意一个 \(k\),删掉第 \(k\) 行和第 \(k\) 列,然后利用交换两行行列式取反,一行减去另一行的倍数行列式不变,变成上三角矩阵,就是只有 \(i\le j\) 时 \(a_{i,j}\) 有值,利用上三角矩阵的行列式是对角线的乘积求解即可。

拉格朗日插值还原多项式

插值 - OI Wiki (oi-wiki.org)

拉格朗日插值公式:

\[f(x)=\sum ^n_{i=1} y_i \prod _{i\neq j} \frac{x-x_j}{x_i-x_j} \]

最暴力模拟的话可以 \(O(n^3)\),利用多项式快速插值可以做到 \(O(n\log^2 n)\)。

代码

点击开 D
const int N=59,moder=998244353;
int n,K,fa[N]={},D[N][N]={},f[N]={},h[N]={};
bool is[N][N]={};
int add(int x,int y) { return x+y>=moder?x+y-moder:x+y; }
int sub(int x,int y) { return x<y?x-y+moder:x-y; }
int mul(int x,int y) { return (ll)x*y%moder; }
int Add(int &x,int y) { return x=x+y>=moder?x+y-moder:x+y; }
int Sub(int &x,int y) { return x=x<y?x-y+moder:x-y; }
int Mul(int &x,int y) { return x=(ll)x*y%moder; }
int kuai(int a,int b) { ll rey=1,temp=a; for(;b;b>>=1) { if(b&1) rey=rey*temp%moder; temp=temp*temp%moder; } return rey; }
int get(int x) {
	int i,j,k,rey=1,op=0,inv,muler;
	memset(D,0,sizeof(D));
	for(i=0;i<n;++i)
		for(j=0;j<n;++j)
			if(i!=j)
				D[i][j]=is[i][j]?1:x,
				Add(D[i][i],D[i][j]),
				D[i][j]=sub(0,D[i][j]);
	for(i=1;i<n;++i) {
		if(!D[i][i]) {
			for(j=i+1;j<n;++j)
				if(D[j][i]) {
					for(k=1;k<n;++k)
						swap(D[i][k],D[j][k]);
					op^=1; break;
				}
		}
		Mul(rey,D[i][i]);
		inv=kuai(D[i][i],moder-2);
		for(j=i+1;j<n;++j) {
			muler=mul(D[j][i],inv);
			for(k=1;k<n;++k)
				Sub(D[j][k],mul(D[i][k],muler));
		}
	}
	if(op) rey=sub(0,rey);
	return rey;
}
void lag() {
	int i,j,k,tot,muler,g[N]={},oldg[N]={};
	for(i=1;i<=n;++i) {
		memset(g,0,sizeof(g)),g[0]=1;
		for(j=1,tot=0;j<=n;++j)
			if(i!=j) {
				memcpy(oldg,g,sizeof(oldg));
				++tot;
				muler=sub(i,j),muler=kuai(muler,moder-2);
				for(k=0;k<=tot;++k)
					g[k]=mul(sub(k?oldg[k-1]:0,mul(oldg[k],j)),muler);
			}
		for(j=0;j<=tot;++j)
			Add(h[j],mul(g[j],f[i]));
	}
	return ;
}
int main()
{
	usefile("b");
	int i,ans=0;
	read(n,K);
	for(i=1;i<n;++i)
		read(fa[i]),
		is[i][fa[i]]=is[fa[i]][i]=true;
	for(i=1;i<=n;++i)
		f[i]=get(i);
	lag();
	for(i=0;i<=K;++i)
		Add(ans,h[i]);
	printf("%d\n",ans);
	return 0;
}

标签:拉格朗,moder,int,5034,矩阵,插值,NOI2017,权值,3.28
From: https://www.cnblogs.com/fydj/p/18264017/GMOJ5034

相关文章

  • 3.28
     今天准备设计一下地铁查询系统的整体架构,因为北京地铁的线路繁多,所以在设计数据库表时就存在很大问题,如何设计才能在存储数据时以及前后端处理数据时,都简便一些。当然如果一方面过度的方便就证明另一方面极其困难,在博客园找到了15年地铁站点的数据,但是对比现在差的太多了,所以我......
  • 九龙城寨之围城迅雷下载[AVI/3.28GB]超高清版画质[HD1080p]
    《九龙城寨之围城》是一部由中国导演执导的电影,该片根据真实故事改编,讲述了九龙城寨在20世纪90年代的一次重大事件。本文将从剧情、演员表现、电影风格等方面对该电影进行分析。 首先,该片的剧情非常紧凑且扣人心弦。故事发生在20世纪90年代的香港九龙城寨,这座庞大的城......
  • P5607 [Ynoi2013] 无力回天 NOI2017
    [Ynoi2013]无力回天NOI2017-洛谷看到题目可以想到线性基线性基可以做到\(O(\logA)\)加入,\(O(\logA)\)查询,\(O(\log^2A)\)合并考虑直接暴力的用线段树维护每个节点的线性基,可以做到\(O(n\logn\log^2A)\)但有区间修改?差分转单点修,发现线性基\(a_{[l......
  • 3.28
    这个任务中,你需要实现前端上传Excel文件,然后将文件传输到后端,后端再将Excel文件解析并将数据插入数据库。下面是一种可能的实现方法:前端(Vue.js):使用 <el-upload> 组件实现文件上传功能,并绑定一个上传文件的事件。通过Axios或其他方式将上传的Excel文件发送到后端。......
  • 就业班 第二阶段 2401--3.28 day8 shell之循环控制
    七、shell编程-循环结构shell循环-for语句foriin{取值范围}  #for关键字i变量名in关键字取值范围格式12345do          #do循环体的开始循环体done         #done循环体的结束#!/usr/......
  • 3.28
    【JavaWEB/表单提交/Tomcat】报404,显示“请求资源[…/Servlet]不可 1、首先检查代码,是否是报错的/爆红的,这里我不截图了。大家自行检查。2、点开WEB-INF,点开web.xml,查看自己是否为你要是用的servlet添加了映射。  很明显。我们是加了的。如果每加,请小伙伴按照我的格式添加......
  • 3.28毕设
    vue3响应式数据,有两种实现方式即ref()和reactive()ref=======>可以基本数据类型,也可以定义对象类型的响应式数据,reactive======>只可以定义对象数据类型的响应式数据 ref()包裹的数据使用时,应加上.value,这里推荐一个插件,ref()定义的可以数据自动补齐.value,防止忘记, 下......
  • NOI2017 蔬菜
    传送门NOI的题果然是非常的难且有意思。还有就是推荐一下command_block的题解。这题的题意比较难。题意:有\(n\)种菜,初始每种菜有\(c_i\)个,单价\(a_i\),如果不出售每天会变质\(x_i\)棵。第一次卖这种菜会获得\(s_i\)的奖励。每天至多卖\(m\)个菜。给出\(q\)次询......
  • 3.28 第一次结对笔记
     今天准备设计一下地铁查询系统的整体架构,因为北京地铁的线路繁多,所以在设计数据库表时就存在很大问题,如何设计才能在存储数据时以及前后端处理数据时,都简便一些。当然如果一方面过度的方便就证明另一方面极其困难,在博客园找到了15年地铁站点的数据,但是对比现在差的太多了,所以我......
  • 2024.3.28
    2024.3.28【浮世景色百千年依旧,人之在世却如白露与泡影。】Thursday二月十九<theme=oi-"string">今天神奇模拟赛)A.水水题题目描述给定若干个串,对于每个串,求出所有可能的串使得这些可能的串既是原串的前缀又是原串的后缀。输入格式若干行,表示若干个原串输出格式......