题解 CF1580B Mathematics Curriculum
Miko35
·
·
题解
题意：
求满足以下条件的排列个数：
- 长度为 n。
- 恰有 k 个数满足：所有包含这个数的区间中，不同的最大值的个数恰有 m 个。
除去这个 100 的范围，是一道好的练手题。
将“所有包含这个数的区间中，不同的最大值的个数恰有 $m$ 个”的数称作 $m$ - 好数，那么用 $f_{i,j,k}$ 表示：长度为 $i$ 的序列，$k$ - 好数有 $j$ 个的方案数。
考虑如何转移 $f_{i,j,k}$：枚举最大值的位置 $p$，左右两边只需要保留偏序关系，可以看作是长度为 $p-1$ 和 $i-p$ 的两个排列，划分方案数就是 $\dbinom{n-1}{p-1}$。
跨越最大值的区间显然只会对不同最大值个数有 $1$ 的贡献，需要找的其实是左右两边的 $(k-1)$ - 好数。所以可以再枚举一维 $c$ 表示左半边的 $(k-1)$ - 好数个数，右半边即为 $j-c-[k=1]$（中间的最大值是 $1$ - 好数，要判掉）。
所以有转移：
$$f_{i,j,k}=\sum_p \binom{n-1}{p-1}\sum_c f_{p-1,c,k-1}\cdot f_{i-p,j-c-[k=1],k-1}$$
时间复杂度 $O(n^5)$，需要注意的是：
- $p=1$ 或 $p=i$ 需要特判。
- 如 $j=0$ 且 $k>i$ 的边界情况需要注意，按定义计算。
- 乘法很慢，可以先判断是否为 $0$ 再转移。
```cpp
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define rgi register int
#define FOR(i,a,b) for(rgi i=a,i##i=b;i<=i##i;++i)
#define ROF(i,a,b) for(rgi i=a,i##i=b;i>=i##i;--i)
using namespace std;
const int N=110;
int n,m,K,P,f[N][N][N],fac[N],C[N][N];
inline int get(int i,int j,int k){
if(!j&&(k>i||k<1))return fac[i];
return f[i][j][k];
}
signed main(){
scanf("%d%d%d%d",&n,&m,&K,&P),f[1][1][1]=C[0][0]=fac[0]=1;
FOR(i,1,n){
C[i][0]=1,fac[i]=1ll*fac[i-1]*i%P;
FOR(j,1,i)C[i][j]=(C[i-1][j]+C[i-1][j-1])%P;
}
FOR(i,2,n)FOR(j,0,min(i,K))FOR(k,1,min(i-j+1,m)){
rgi G=j-(k==1),X,Y;
f[i][j][k]=(get(i-1,G,k-1)*2)%P;
FOR(p,2,i-1)FOR(c,0,min(p,G))if((X=get(p-1,c,k-1))&&(Y=get(i-p,G-c,k-1))){
f[i][j][k]=(f[i][j][k]+1ll*X*Y%P*C[i-1][p-1])%P;
}
}
printf("%d",f[n][K][m]);
return 0;
}
```