快速题解to agc024E
pengyule
2022-01-06 06:57:53
https://atcoder.jp/contests/agc024/tasks/agc024_e
模拟这个过程。
其中 `#` 代表其他的数，不重要，我们关键看 `x` 的动作。
为了不重复统计，我们规定 **$x$ 是一个连续相同数字段的起头**。
在左边能插入数的充要条件是，插入的数**大于** $x$。
为什么？有归纳法：
1. 第一次（第一行到第二行）显然需要大于；
2. 后面只需要以现在左边 `#` 全大于 $x$ 为前提，这种情况下由于我们规定了 $x$ 是起头的因此很容易意会。
我们设 `x` 位置值为 $x$，其左侧（不含）有 $k$ 个 `#`，这是在考虑 $A_i$，$A_i$ 里只能用 $[j,m]$ 中的数，为 $f(i,j)$。
那么
$$
f(i,j)=\sum_{x=j}^{m}\sum_{k=0}^{i-1}f(k,x+1)f(i-1-k,j){{i-1}\choose{k}}
$$
第一个 $f(k,x+1)$ 是左边一坨 `#` 的方案，同理…是右边的，而为什么要乘组合数？
因为上面绿色的 `+`，虽然左边和右边所加的数的**集合**是确定的，但操作序列的顺序是有区别的，我们可以任意决定这些 `+` 号在竖直方向的相对位置！
$O(n^5)$。接着发现组合数只跟 $i,k$ 相关便可以预处理。$O(n^4)$。
最后便是前缀和优化。$O(n^3)$。
由于 $x$ 只出现了一次，而且每次都是查 $j+1\sim m+1$ 这个后缀，因此通过结合律可以知道
$$
f(i,j)=\sum_{k=0}^{i-1}t(k,j)f(i-1-k,j){{i-1}\choose{k}},\text{where }t(i,j)=f(i,j+1)+f(i,j+2)+...+f(i,m+1)
$$
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N=305;
int n,m,mod,f[N][N],t[N][N],C[N][N];
int main(){
cin>>n>>m>>mod;
C[0][0]=1;
for(int i=1;i<=n;i++){
C[i][0]=1;
for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
for(int i=1;i<=m+1;i++)f[0][i]=1;for(int i=m;i;i--)t[0][i]=t[0][i+1]+f[0][i+1];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
for(int k=0;k<i;k++)
(f[i][j]+=1ll*t[k][j]*f[i-1-k][j]%mod*C[i-1][k]%mod)%=mod;
for(int j=m;j;j--)t[i][j]=(t[i][j+1]+f[i][j+1])%mod;
}
cout<<f[n][1];
}
```