题解 AT3962 【[AGC024E] Sequence Growing Hard】
FZzzz
·
·
题解
下文中的 m 就是原题面中的 k，因为不然循环变量就不够用了。
在连续的一段相等的字符中的任意一个位置插入一个这种字符，得到的结果是相同的。出于去除重复计数和简化限制两方面的考虑，我们将限制改为：后一个字符比插入的字符小。那么我们可以直接对每次插入的位置和插入的字符计数，就能够统计到所有不同的方案。
这样还是不易于统计，再做一步转化，把每个字符的位置用它被插入的时间表示。那么我们需要做的即是对每次操作，选择之前的一次操作表示这次插在之前插的位置前面。特别地，选择 $0$ 操作表示这次插在最后面。
这样形成了一个树形结构，$0$ 是根节点。那么问题转化为对一个有标号的树计数，每个点有一个 $[0,m]$ 的权值，根的权值和编号都为 $0$，要满足儿子的编号和权值都比父亲大。
设计一个 dp，$f_{i,j}$ 表示根的权值为 $j$ 的 $i$ 个点的树的数量。转移时枚举编号最小的儿子的编号和数量，相当于把这个子树的编号插到其他子树去。有转移方程：
$$f_{i,j}=\sum_{k=1}^{i-1}\sum_{h=j+1}^m\binom{i-2}{k-1}f_{k,h}f_{i-k,j}$$
预处理组合数，后缀和优化即可。时间复杂度 $O(n^2m)$。
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll readint(){
ll x=0;
bool f=0;
char c=getchar();
while(!isdigit(c)&&c!='-') c=getchar();
if(c=='-'){
f=1;
c=getchar();
}
while(isdigit(c)){
x=x*10+c-'0';
c=getchar();
}
return f?-x:x;
}
const int maxn=300+5;
int n,m;
ll p,C[maxn][maxn],f[maxn][maxn],s[maxn][maxn];
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
n=readint();
m=readint();
p=readint();
for(int i=0;i<=n+1;i++){
C[i][0]=1;
for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%p;
}
for(int i=0;i<=m;i++){
f[1][i]=1;
s[1][i]=m-i+1;
}
for(int i=2;i<=n+1;i++) for(int j=m;j>=0;j--){
for(int k=1;k<i;k++)
f[i][j]=(f[i][j]+s[k][j+1]*f[i-k][j]%p*C[i-2][k-1]%p)%p;
s[i][j]=(s[i][j+1]+f[i][j])%p;
}
printf("%lld\n",f[n+1][0]);
#ifdef LOCAL
fprintf(stderr,"%f\n",1.0*clock()/CLOCKS_PER_SEC);
#endif
return 0;
}
```
这是这题现在的主流做法，但是其实还有更简洁巧妙的 dp 方式。设 $f_{i,j}$ 为 $j$ 个节点权值不大于 $i$ 的树的个数。
每次枚举权值小于 $i$ 的节点的个数 $k$，那么另外 $j-k$ 节点一定全是叶子。考虑从 $f_{i-1,k}$ 转移时的转移系数，我们需要的是给这 $j-k$ 个点找到父亲，再给所有点重新分配编号。我断言，这样做的方案数相当于把 $j$ 个有区别元素分配进 $k$ 个无区别非空集合里。
建立这两件事之间的双射。把这些集合按照各自的最小元排序，然后按照 $k$ 个点原来的标号顺序对应到这 $k$ 个点。令剩下这些元素对应到新加进来的 $j-k$ 个点，每个点的父亲为它集合内的最小元对应的点。这样可以证明两个方案数是相等的。
举个例子，假如我本身有一棵两个节点的树，现在新加入一个节点，那么：
- 集合分配是 $\{\{0\},\{1,2\}\}$，那么原来的点编号是 $0$ 和 $1$，新加入的点编号是 $2$，父亲是 $1$；
- 集合分配 $\{\{0,1\},\{2\}\}$，那么原来的点编号是 $0$ 和 $2$，新加入的点编号是 $1$，父亲是 $0$；
- 集合分配是 $\{\{0,2\},\{1\}\}$，那么原来的点编号是 $0$ 和 $1$，新加入的点编号是 $2$，父亲是 $0$。
这样就把两个问题的方案一一对应。
那么转移方程就是：
$$f_{i,j}=\sum_{k=1}^{j-1}\begin{Bmatrix}j\\k\end{Bmatrix}f_{i-1,k}$$
预处理第二类斯特林数，时间复杂度仍为 $O(n^2m)$。
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll readint(){
ll x=0;
bool f=0;
char c=getchar();
while(!isdigit(c)&&c!='-') c=getchar();
if(c=='-'){
f=1;
c=getchar();
}
while(isdigit(c)){
x=x*10+c-'0';
c=getchar();
}
return f?-x:x;
}
const int maxn=300+5;
int n,m;
ll p,S[maxn][maxn],f[maxn][maxn];
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
n=readint();
m=readint();
p=readint();
S[0][0]=1;
for(int i=1;i<=n+1;i++){
for(int j=1;j<=i;j++)
S[i][j]=(S[i-1][j]*j%p+S[i-1][j-1])%p;
}
f[0][1]=1;
for(int i=1;i<=m;i++) for(int j=1;j<=n+1;j++)
for(int k=1;k<=j;k++)
f[i][j]=(f[i][j]+f[i-1][k]*S[j][k]%p)%p;
printf("%lld\n",f[m][n+1]);
#ifdef LOCAL
fprintf(stderr,"%f\n",1.0*clock()/CLOCKS_PER_SEC);
#endif
return 0;
}
```
遗留问题：
1. 能否对第一个递推式，通过代数推导得到第二个递推式？
2. 在 $m$ 较大时我们显然可以矩阵快速幂 $O(n^3\log m)$（可能可以通过 BM 和特征多项式做到 $O(n^2+n\log n\log m)$？），但能否在 $o(n^2)$ 时间内解决？
~~有没有老哥教教我啊。~~