题解 P8554【心跳】
whiteqwq
·
·
题解
P8554 心跳 解题报告：
更好的阅读体验
题意
定义一个排列上的函数 f(p,i) 表示序列 p 去除 i 位置后前缀最大值个数。对于所有长度为 n 的排列 p，生成序列 a_i=f(p,i)。试计数值域 [m,n]，且能被生成的 a 序列数量。
## 分析
hzr 场切了，有点恐怖的。
下面记 $g(p)$ 为不去除任何位置的前缀最大值个数。
首先有一个结论，对于两个 $g$ 不相等的排列，其生成的 $a$ 序列不可能有交。
经过初步地观察，我们能得知：
- 若去除的位置不是前缀最大值，$f(p,i)=g(p)$；
- 否则，$f(p,i)$ 为 $i$ 后面大于 $[1,i-1]$ 所有数的单调栈大小加 $g(p)-1$。
于是我们可以将序列里的数分成三个部分：前缀最大值，可能成为前缀最大值的数（下文称其为有用的数），其他。
将排列按照前缀最大值划分成若干段，那么前缀最大值的 $f(p,i)$ 就是其对应段有用的数数量加上 $g(p)-1$。
我们并不关心有用的数的位置，只关心其数量，于是可以将一段内所有有用的数保留顺序提前，然后生成一个仅包含 $\{0,1,2\}$ 的序列，$0$ 对应前缀最大值，$1$ 对应有用的数，$2$ 对应没用的数。（称这种序列为颜色序列）
我们想直接 dp 来计数颜色序列，但必须先知道任意颜色序列是否都存在一个对应的排列 $p$。
考虑一种排列的生成方式：从前往后加入数字，维护目前前缀 $[1,i]$ 离散化后的结果，每次插入一个 $[1,i+1]$ 内的数字并将大于等于其的数字加一（其实就是在值域上插入数字）。那么插入 $i+1$ 就对应插入一个 $0$，插入 $i$ 就对应插入一个 $1$，否则就是插入一个 $2$。
只需保证第一个位置是 $0$，第二个位置是 $0/1$ 即可。
但是不同的颜色序列可能对应相同的 $a$ 序列，算重的原因实际上就是 $201\text{x}$ 与 $012\text{x}$ 等价，以及 $01\text{x}$ 与 $22$ 等价（$\text{x}=\{0,2\}$），于是我们只需保证序列中不存在 $201\text{x}$ 子段与 $22$ 后的 $01\text{x}$ 子段即可。
令 $f_{i,j,0/1/2/3,0/1/2}$ 表示 dp 了 $i$ 个位置，前缀最大值个数为 $j$，上一个为 $0$、$1$（长度 $=1$）、$1$（长度 $>1$）、$2$，无限制、当前段不能只有 $1$ 个 $1$，后面所有段不能只有 $1$ 个 $1$，直接转移即可。
$m$ 的限制很好处理，要么前缀最大值数量大于 $m$，要么前缀最大值数量等于 $m$ 且没有一个前缀最大值段没有有意义的数，随便改改转移方程就好了。
复杂度 $O(n^2)$。
## 代码
写不动，借鉴了官方题解的波特状态。
```cpp
#include<stdio.h>
#include<string.h>
const int maxn=2005,mod=1000000007;
int n,m,ans,now;
int f[2][maxn][11],g[11],h[11];
void solve(int typ){
now=0,f[0][1][1]=1;
if(typ==0)
f[0][2][0]=1;
for(int i=3;i<=n;i++){
now^=1,memset(f[now],0,sizeof(f[now]));
for(int j=1;j<=i;j++){
for(int c=0;c<=10;c++){
g[c]=f[now^1][j][c];
if(typ&&(c==0||c==5||c==8))
g[c]=0;
}
h[0]=h[3]=(0ll+g[0]+g[1]+g[2]+g[8]+g[10])%mod;
h[1]=f[now^1][j][0],h[2]=(g[1]+g[2])%mod;
h[4]=(0ll+g[3]+g[4]+g[5]+g[7])%mod;
h[5]=(0ll+g[4]+g[5]+g[7])%mod;
h[6]=f[now^1][j][5],h[7]=(g[6]+g[7])%mod;
h[8]=g[3];
h[9]=f[now^1][j][8],h[10]=(g[9]+g[10])%mod;
for(int c=0;c<=10;c++){
int nxt=j+(c==0||c==5||c==8);
f[now][nxt][c]=(f[now][nxt][c]+h[c])%mod,h[c]=0;
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
solve(0);
for(int i=m+1;i<=n;i++)
for(int c=0;c<=10;c++)
if(c!=6&&c!=9)
ans=(ans+f[now][i][c])%mod;
memset(f,0,sizeof(f));
solve(1);
for(int c=0;c<=10;c++)
if(c!=0&&c!=5&&c!=6&&c!=8&&c!=9)
ans=(ans+f[now][m][c])%mod;
printf("%d",ans);
return 0;
}
```