已完成今日T2大学习

byd周末一直在安东星开线忘记写了

省流：

多头出的题被forest组成模拟赛喂给联考被出来外培的我给吃了。

鉴定为师出同门导致脑电波对上了。

sol

容易发现和原本的前缀最大值关系密切。

具体而言，一个位置 $i$ 是前缀最大值，那么其会对所有不等于 $i$ 的位置上的 $a$ 做贡献。否则，这个位置是之前某个位置删除之后新增的前缀最大值。容易发现对于一个点 $j$，其作为新增的前缀最大值，只可能贡献到其之前的第一个前缀最大值 $i$ 的 $a$ 数组上。

然后通过打表猜测在 $n>2$ 时，一个合法的序列 $a$ 的所有可能的来源的 $p$ 的前缀最大值数量是相同的。实际上也的确如此，证明不会。（$n>2$ 时成立，所以完全可以给你把数据范围开成 $1\le n$ 来阴你一把。）

继续观察，假设当前 $a$ 数组对应的 $p$ 的前缀最大值个数是 $k$，且我们知道了 $p$ 的前缀最大值的位置集合 $S$。而这些位置在 $a$ 上的值能取到多少能？假设当前位置到下一个前缀最大值之间的空位个数为 $x$，则当前位置合法的取值范围是 $[k-1,k-1+x]$。（corner：当前位置是 $1$ 且 $x\not=0$，则取值范围是 $[k,k-1+x]$。）

证明：只考虑值的相对大小地插入排列的元素，首先将前缀最大值插入到序列的对应位置上，两个前缀最大值之间的位置只对前者做贡献，且可以通过在当前前缀最大值和上一个前缀最大值的值域之间插入元素 （注意这里也解释了 corner 的原因）所以可以任意调整每一个位置是否做贡献。

我们选取当前位置之后连续的一段非前缀最大值作为删去当前节点之后新增贡献的位置，并将当前位置和其之后这些被选取的位置称为一段。则 $a$ 数组可以表示为若干个互不相交的段。但是注意当段长为 $2$ 时，这一段的起始元素在 $a$ 上是 $k$，无法和其他平凡的位置区分开，一个 $a$ 可能对应多种划分方式，故无法直接构成双射。

不过解决方式很简单，我们在考虑完所有长度不是 $2$ 的线段之后，让这些长度为 $2$ 的线段尽可能地靠前即可。

于是我们现在就可以用一个不交线段的覆盖方式来表示 $a$ 了！

那么对前者计数就容易计数出合法的 $a$ 的数量。

至于对于值域的限制，显然，当我们选取的段数 $>m$ 时，$a$ 的值域一定 $\ge m$。否则恰好选择 $m$ 段且不存在单独的一段时值域 $\ge m$。

讲到这里其实读者随便列个 dp 就能做出来了。下文是我的考场做法。

考虑设 $dp_{i,j,0/1,0/1}$ 表示考虑了前 $i$ 位，此时已经填了 $j$ 个线段了，决定当前位置之后还能否继续填长度为 $2$ 的段，上一段是否是长度为 $2$ 的段。

如果还可以填长度为 $2$ 的段则转移是平凡的。

否则只能新增一段 $len\not=2$ 的段，（前缀和优化）或者填一个空位。

如果当前结尾不是填的 $2$ 的段，则转移是平凡的。

否则，可以直接填或者空一位填长度 $\not=2$ 的段。如果还可以继续填长度为 $2$ 的段，则可以填长度为 $2$ 的段。

然后再写一个 $dp$ 处理不能有长度为 $1$ 的段的情况。

还要注意如果 $1$ 开头的段长度为 $1$，则下一位不能是空位。（对应前文提到的corner。）

还要注意代码中是在填完一个长度为 $2$ 的段之后决定是否还能继续填，所以初始化为 $dp_{0,0,0,0}=dp_{0,0,1,0}=1$。

code

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define per(i,a,b) for(register int i=(a);i>=(b);--i)
#define edge(i,u) for(int i=head[u];i;i=e[i].next)
#define lc (u<<1)
#define rc (u<<1|1)
#define pii pair<int,int>
#define pdd pair<double,double>
#define mp make_pair
#define pb push_back
#define fst first
#define sed second
#define Max(a,b) (a=max(a,b))
#define Min(a,b) (a=min(a,b))
using namespace std;
const int N=7000+10,M=1e6+10,inf=1e9,mod=1e9+7;
const double eps=1e-6;
bool MS;int used;
struct modint{
...//取模类
};
int n,m;
modint f[5][N][2][2];//驻波的第三维的状态好像和上文描述的是反的。
modint sum[5][N][2][2];
modint sum_[N][2][2];
modint sol(int m)
{
	memset(f,0,sizeof f);
	memset(sum,0,sizeof sum); 
	sum[0][0][0][0]=f[0][0][0][0]=1;
	sum[0][0][1][0]=f[0][0][1][0]=1;
	rep(i,1,n)
	{
		int c=i%5;
		rep(j,0,i)
		rep(k,0,1)
		rep(l,0,1)
		f[c][j][k][l]=
		sum[c][j][k][l]=0;
		
		rep(j,1,i)
		{
			if(i-3>=0)
			{
				f[c][j][0][0]+=sum[(i-3)%5][j-1][0][0];
				f[c][j][0][0]+=sum[(i-3)%5][j-1][0][1];
					
				f[c][j][1][0]+=sum[(i-3)%5][j-1][1][0];
				f[c][j][1][0]+=sum[(i-3)%5][j-1][1][1];
			}
			if(i>=6)
			{
				f[c][j][0][0]+=sum[(i-4)%5][j-1][0][0]-sum_[j-1][0][0];
				f[c][j][0][0]+=sum[(i-4)%5][j-1][0][1]-sum_[j-1][0][1];
				
				f[c][j][1][0]+=sum[(i-4)%5][j-1][1][0]-sum_[j-1][1][0];
				f[c][j][1][0]+=sum[(i-4)%5][j-1][1][1]-sum_[j-1][1][1];
			}
			if(i>=2)
			{
				f[c][j][0][1]+=f[(i-2)%5][j-1][0][0];
				f[c][j][0][1]+=f[(i-2)%5][j-1][0][1];
				
				f[c][j][1][1]+=f[(i-2)%5][j-1][0][0];
				f[c][j][1][1]+=f[(i-2)%5][j-1][0][1];
				
				if(i!=3)
				f[c][j][1][1]+=f[(i-2)%5][j][1][0];
				f[c][j][1][1]+=f[(i-2)%5][j][1][1];
			}
		}
		rep(j,0,i)
		rep(k,0,1)
		rep(l,0,1)
		sum[c][j][k][l]=sum[(i-1)%5][j][k][l]+f[c][j][k][l];
		if(i==1)
		rep(j,0,i)
		rep(k,0,1)
		rep(l,0,1)
		sum_[j][k][l]=sum[i][j][k][l];
	}
	modint ans=0;
	ans+=f[n%5][m][1][0]+f[n%5][m][1][1];
	ans+=f[(n-1)%5][m][1][0]+f[(n-1)%5][m][1][1];
	return ans; 
}
bool MT;
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	sum[0][0][0][0]=f[0][0][0][0]=1;
	sum[0][0][1][0]=f[0][0][1][0]=1;
	rep(i,1,n)
	{
		int c=i%5;
		rep(j,0,i)
		rep(k,0,1)
		rep(l,0,1)
		f[c][j][k][l]=
		sum[c][j][k][l]=0;
		
		rep(j,1,i)
		{
			if(i-3>=0)
			{
				f[c][j][0][0]+=sum[(i-3)%5][j-1][0][0];
				f[c][j][0][0]+=sum[(i-3)%5][j-1][0][1];
					
				f[c][j][1][0]+=sum[(i-3)%5][j-1][1][0];
				f[c][j][1][0]+=sum[(i-3)%5][j-1][1][1];
			}
			if(i>=6)
			{
				f[c][j][0][0]+=sum[(i-4)%5][j-1][0][0]-sum_[j-1][0][0];
				f[c][j][0][0]+=sum[(i-4)%5][j-1][0][1]-sum_[j-1][0][1];
				
				f[c][j][1][0]+=sum[(i-4)%5][j-1][1][0]-sum_[j-1][1][0];
				f[c][j][1][0]+=sum[(i-4)%5][j-1][1][1]-sum_[j-1][1][1];
			}
			f[c][j][0][0]+=f[(i-1)%5][j-1][0][0];
			f[c][j][0][0]+=f[(i-1)%5][j-1][0][1];
			f[c][j][1][0]+=f[(i-1)%5][j-1][1][0];
			f[c][j][1][0]+=f[(i-1)%5][j-1][1][1];
			if(i>=2&&i!=3)
			f[c][j][0][0]+=f[(i-2)%5][j-1][0][1],
			f[c][j][1][0]+=f[(i-2)%5][j-1][1][1];
			if(i>3)
			f[c][j][0][0]+=f[(i-2)%5][j-1][0][0],
			f[c][j][1][0]+=f[(i-2)%5][j-1][1][0];
			
			if(i>=2)
			{
				f[c][j][0][1]+=f[(i-2)%5][j-1][0][0];
				f[c][j][0][1]+=f[(i-2)%5][j-1][0][1];
				
				f[c][j][1][1]+=f[(i-2)%5][j-1][0][0];
				f[c][j][1][1]+=f[(i-2)%5][j-1][0][1];
				
				if(i-2!=1)
				f[c][j][1][1]+=f[(i-2)%5][j][1][0];
				f[c][j][1][1]+=f[(i-2)%5][j][1][1];
			}
		}
		
		rep(j,0,i)
		rep(k,0,1)
		rep(l,0,1)
		sum[c][j][k][l]=sum[(i-1)%5][j][k][l]+f[c][j][k][l];
		if(i==1)
		rep(j,0,i)
		rep(k,0,1)
		rep(l,0,1)
		sum_[j][k][l]=sum[i][j][k][l];
	}
	modint ans=0;
	rep(i,m+1,n)ans+=f[n%5][i][1][0]+f[n%5][i][1][1];
	rep(i,m+1,n)ans+=f[(n-1)%5][i][1][0]+f[(n-1)%5][i][1][1];//考虑空位 
	ans+=sol(m);
	cout<<ans<<'\n'; 
	cerr<<"Memory:"<<(&MS-&MT)/1048576.0<<"MB Time:"<<clock()/1000.0<<"s\n";
}

第一次写这么牛的题的题解，如果有没讲清楚的地方欢迎指出。