【2022 NOIP 模拟赛 3】C. 单调栈 做题记录

对于一个序列 $a_{1\dots n}$，定义 $b(a)_{1\dots n}$，满足 $b(a)_i = max\{j | j < i, a_j > a_i\}$。特别地，若 $b(a)_i = 0$，表示不存在这样的 $j$。

给定一个序列 $p_{1\dots n}$ 和值域大小 $m$，满足 $-1\le p<i$，请求出有多少个序列 $a_{1\dots n}$ 满足：

• $1\le a_i\le m$
• 对于所有满足 $p_i\not=-1$ 的 $i$，都有 $b(a)_i=p_i$

答案对 $10^9+7$ 取模，满足答案至少为 $1$。

$1\le n\le 300,1\le m\le 10^5$。

观察到若 $p_i\not=-1$，那么一定有 $a_{[p_i+1,i]}\le a_i,a_i<a_{p_i}$。

所以由于答案至少为 $1$，那么若对于所有满足 $p_i\not=-1$ 的 $i$ 都从 $i$ 向 $p_i$ 连一条有向边，这些边肯定不会相交：

观察到这些边构成了包含关系，并且内层的值一定小于等于外层的，所以不难想到堆，那么考虑建立一棵树，跑树形 dp。不难发现，关系只有大于和大于等于两种，所以考虑给树加上边权，边权为 $1$ 表示父亲的值要大于儿子，边权为 $0$ 表示父亲的值要大于等于儿子。

首先虚拟出一个点 $n+1$，令 $p_{n+1}=0$。这么做是为了让所有 $p_i=0$ 联通，最后能够组成一棵树。

考虑 $p_i=-1$ 的点。显然，设 $x$ 表示包含 $i$ 的最内层的边的右端点，在树上只要让 $i$ 的父亲为 $x$，边权为 $0$ 即可。特别的，若 $x=n+1$，那么要让 $i$ 的父亲为 $0$，边权为 $0$：

接下来考虑 $p_i\not=-1$ 的点，朴素的想法是在树上让 $i$ 的父亲为 $p_i$，边权为 $1$。但是考虑如下情况：

显然要满足 $a_4\le a_6<a_2$，那么在树上这样建边即可：

代码实现也不难，倒着扫即可。

建出树之后直接跑 dp 即可，在此不过多赘述。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

inline int read()
{
	int s=0,w=1,c=getchar();
	while(c<'0'||c>'9') c=='-'?w=-1,c=getchar():c=getchar();
	while(c>='0'&&c<='9') s=s*10+c-'0',c=getchar();
	return s*w;
}

const int S=305,MS=100005,SS=1000005,p=1000000007;

int n,m;
int pre[S],lst[S];
int esum,to[SS],c[SS],nxt[SS],h[S];
int dp[S][MS];

inline void add(int x,int y,int w)
{
	to[++esum]=y;
	c[esum]=w;
	nxt[esum]=h[x];
	h[x]=esum;
}

inline void addd(int &x,int y)
{
	x+=y;
	if(x>=p) x-=p;
}

void dfs(int u)
{
	for(int j=1;j<=m;j++) dp[u][j]=1;
	for(int i=h[u];i;i=nxt[i])
	{
		int v=to[i],w=c[i];
		dfs(v);
		int presm=0;
		for(int j=1;j<=m;j++)
		{
			addd(presm,dp[v][j-w]);
			dp[u][j]=1ll*dp[u][j]*presm%p;
		}
	}
}

int main()
{
	freopen("stack.in","r",stdin);
	freopen("stack.out","w",stdout);
	n=read();
	m=read();
	for(int i=1;i<=n;i++) pre[i]=read();
	for(int i=1;i<=n;i++) lst[i]=i;
	pre[n+1]=0;
	for(int i=n;i>=1;i--)
	{
		if(pre[i]!=-1)
		{
			add(lst[pre[i]],i,lst[pre[i]]==pre[i]&&pre[i]!=0);
			lst[pre[i]]=i;
		}
		else
		{
			for(int j=i+1;j<=n+1;j++)
			{
				if(pre[j]!=-1&&pre[j]<i)
				{
					add(j==n+1?0:j,i,0);
					break;
				}
			}
		}
	}
	dfs(0);
	printf("%d\n",dp[0][m]);
	return 0;
}