首页 > 其他分享 >Tree Depth P 题解

Tree Depth P 题解

时间:2023-03-18 17:57:09浏览次数:35  
标签:ch int 题解 Tree read Depth now 46605 逆序

Tree Depth

题意

\(~~~~\) 对一个排列建立小根笛卡尔树,定义第 \(i\) 个位置的权值为其在笛卡尔树上的深度。求对于所有恰好有 \(k\) 个逆序对的排列,每个位置的权值和对一个大质数取模。
\(~~~~\) \(1\leq n\leq 300\)。

题解

\(~~~~\) 考虑深度这个东西可以怎么刻画,比如说:某个点的祖先数 \(+1\)。

\(~~~~\) 那么由于这是小根笛卡尔树,我们就会发现若一对 \((u,v)\) 中 \(v\) 是 \(u\) 的祖先,那 \(\min_{i=u}^{v-1} a_i>a_v\) ,这样这些东西才不会影响 \(v\).

\(~~~~\) 对于恰好有 \(k\) 个逆序对,经典的dp是我们定义 \(dp_{i,j}\) 表示前 \(i\) 个点,有 \(j\) 个逆序对,那么第 \(i\) 个位置就可以贡献 \([0,i-1]\) 个逆序对。

\(~~~~\) 现在我们枚举点对 \((u,v)\) ,那由于有上面的限制,实际上 \(v\) 的逆序对贡献是固定的,怎么办呢?我们把 \(u\) 前面和 \(v\) 后面的先算出来,然后每次对每个点对撤销 \((u,v)\) 段的影响重新 dp 一遍就好了。

代码

查看代码
#include <bits/stdc++.h>
#define ll long long
#define PII pair<int,int>
#define mp(a,b) make_pair(a,b)
using namespace std;
template<typename T>void read(T &x)
{
    T f=1;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
int n,k,MOD;
inline int Add(int a,int b){return (a+b)%MOD;}
inline int Dec(int a,int b){return (a-b+MOD)%MOD;}
inline int Mul(int a,int b){return 1ll*a*b%MOD;}
inline int qpow(int a,int b)
{
	int ret=1;
	while(b)
	{
		if(b&1) ret=Mul(ret,a);
		b>>=1;a=Mul(a,a);
	}
	return ret;
}
int f[2][46605],Sum[46605],g[46605],Siz,Ans[46605];
void Cancel(int x)
{
	memset(g,0,sizeof(g));
	int now=MOD-1; g[0]=1;
	for(int i=1;i<=Siz-x;i++)
	{
		if(i>x) now=Add(now,g[i-x-1]);
		now=Dec(now,g[i]=Add(f[n&1][i],now));
	}
}
int main() {
	read(n);read(k);read(MOD);
	for(int i=1;i<=n;i++)
	{
		Sum[0]=f[i&1][0]=1; Siz+=i-1;
		for(int j=1;j<=Siz;j++)
		{
			f[i&1][j]=Sum[j]=Add(Sum[j-1],f[!(i&1)][j]);
			if(j>=i) f[i&1][j]=Dec(f[i&1][j],Sum[j-i]);
		}
	}
	for(int i=1;i<=n;i++) Ans[i]=f[n&1][k];
	for(int Now=1;Now<n;Now++)
	{
		Cancel(Now);
		for(int i=1;i<=n-Now;i++)
		{
			if(Now<=k) Ans[i]=Add(Ans[i],g[k-Now]);
			Ans[i+Now]=Add(Ans[i+Now],g[k]);
		}
	}
	for(int i=1;i<=n;i++) printf("%d ",Ans[i]);
	return 0;
}
/*
瑶草一何碧,春入武陵溪。溪上桃花无数,花上有黄鹂。我欲穿花寻路,直入白云深处,浩气展虹霓。只恐花深里,红露湿人衣。
坐玉石,欹玉枕。拂金徽。谪仙何处,无人伴我白螺杯。我为灵芝仙草,不为朱唇丹脸,长啸亦何为。醉舞下山去,明月逐人归。
*/

标签:ch,int,题解,Tree,read,Depth,now,46605,逆序
From: https://www.cnblogs.com/Azazel/p/17231336.html

相关文章

  • webpack原理(2):ES6 module在Webpack中如何Tree-shaking构建
    Tree-shaking最早由打包工具Rollup 提出DCE作用于模块内(webpack的DCE通过UglifyJS完成),而Tree-shaking则是在打包的时候通过模块之间的信息打包必须的代码。We......
  • AGC012 题解
    chrislgjeztorAmledzaprofovelmizerdoscarmammeidhaalzengharkawymaynoxialgjeztorRupieillavasphotreywzidha[AGC012A]AtCoderGroupContest普及题......
  • [ABC245E] Wrapping Chocolate题解
    听说没人写,那就来一发。这种偏序问题大概率是要排个序的。将盒子和巧克力视为一个东西,\(c\)视为\(a\),\(d\)视为\(b\),放在一起以\(a\)为第一关键字,\(b\)为第二关键......
  • java.sql.SQLSyntaxErrorException: Table 'test.user' doesn't exist报错问题解决
    以下内容仅供自己学习使用,侵权必删在使用mubatis-plus的时候报错了以下内容java.sql.SQLSyntaxErrorException:Table'test.user'doesn'texist解决方法:2.1在......
  • TreeMap
    TreeMap是有序map,通过key进行排序1.TreeMap是如何实现去重和排序的?TreeMap实现了SortedMap接口,它是一个key有序的Map类。TreeMap的默认排序规则:根据key元素的compareTo......
  • CF1804F Approximate Diameter 题解
    前言在学校机房被学长推荐了这道题,听完正解后惊为天人...简化版题面给定一张无向连通图,定义直径\(d=\max(dis(i,j))\quad(i,j\inN)\),其中\(dis(i,j)\)指的是\(......
  • 【题解】ABC293E Sol
    题目大意给定整数\(A,X,M\),求\(\sum\limits^{X-1}_{i=0}A^i\)对\(M\)取模的值。数据范围:\(1\leA,M\le10^9\),\(1\leX\le10^{12}\)。题目分析直接算显然......
  • 【CF1491H Yuezheng Ling and Dynamic Tree】(分块)
    原题链接题意给定一棵大小为\(n\)的\(1\)为根节点的树,树用如下方式给出:输入\(a_2,a_3,\dots,a_n\),保证\(1\leqa_i<i\),将\(a_i\)与\(i\)连边形成一棵树。接下......
  • h5中audio无法播放问题解决
    H5页面中添加audio标签,通过调用play()方法进行播放音频,电脑可以正常听到音效,微信中打开没有声音。<audioid="audio"ref="audio"class="sound"><sourcesrc="@/st......
  • Tree结构UI优化显示
    整体UI面板绘制参照https://www.cnblogs.com/babashi9527/p/17146645.html接着UI面板的设计;实现树形结构菜单的方式有很多种,每一种优化UI显示的方式可能存在较大差异;我......