【20zr提高组十连测day10】心
首先不同的操作序列一定在某个时刻使数组内容不同，因此我们只需要统计合法的操作序列数量。
一个合法的最终数组形如若干个 \(1,M\)，而且 \(1,M\) 之间可能有若干个 \(x\)，长度为 \(n+1\)。
造成这个数组的操作序列必须满足所有操作 \(1,M\) 按顺序排列，把操作 \(1,M\) 称作关键操作，所有操作 \(x\) 出现在它后面第一个关键操作的后面。
\(u\) 必须出现在 \(v\) 后面，我们连一条 \(u\to v\) 的边，也就是说我们要先遍历 \(v\) 再遍历 \(u\)，拓扑序计数即可，而且是树上拓扑序计数。
树上拓扑序（先选叶子再选儿子的拓扑序）计数可以树形 DP 解决。设 \(f_u\) 表示 \(u\) 在子树的拓扑序数量，显然 \(u\) 的儿子子树间是互不干扰的，但是子树内的顺序是一定的，\(u\) 一定是放在最后，有转移方程：
\[f_u=(siz_u-1)!\prod_{v\in son_u} \frac{f_v}{siz_v!} \]也可以这么算：
\[f_u=siz_u! (\prod_{v\in tree_u} \frac{1}{siz_i} ) \]用数学归纳法证明：
\(n=1\) 时显然成立。
假设 \(n<siz_u\) 时成立。
\[f_u=(siz_u-1)!(\prod_{v \in son_u}\frac{siz_v ! \prod_{i\in tree_v} \frac{1}{siz_v}}{siz_v!})\\ =(siz_u-1)!(\prod_{v\in tree_u,v\not= u} \frac{1}{siz_v})\\ =siz_u! (\prod_{v\in tree_u} \frac{1}{siz_i} ) \]这个也可以理解成每个结点一定在整个子树序列的最后一位，所以答案是所有节点的全排列去掉每个结点在子树其他位置的情况。
回到题目，我们可以做一个 \(n^2\) 的 DP。
\(dp_i\) 表示前 \(i\) 个数字，有若干个空的排列，形成这个排列的操作方案数。
\[\texttt{加上一个和前一位相同的关键数字：}dp_i\cdot \frac{1}{n-i}\to dp_{i+1}\\ \texttt{加上一个和前一位不同的关键数字：}dp_i\cdot \binom{m-2}{k}\cdot \frac{1}{i+k+1}\to dp_{n-i}(0\le k \le n-i-1) \]答案就是 \(dp_n\cdot n!\)。
Code
#include<bits/stdc++.h>
// #define DEBUG
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
using namespace std;
typedef long long ll;
const int N=3e3+4,M=1e8+7,mod=998244353;
int n,m;
ll dp[N];
void add(ll &a,ll b){a= (a+b>mod?a+b-mod:a+b);}
ll ans;
ll inv[N],mul[N];
ll ksm(ll a,ll b){
ll s=1;
while(b){
if(b&1) s=s*a%mod;
a=a*a%mod;
b>>=1;
}
return s;
}
ll ifac[N];
ll del(ll a,ll b){return (a-b<0?a-b+mod:a-b);}
void init(){
inv[1]=1;ifac[0]=ifac[1]=1;
rep(i,2,n) inv[i]=ksm(i,mod-2),ifac[i]=ifac[i-1]*inv[i]%mod;
mul[0]=1;
rep(i,1,n){
if(m-2-i+1<=0){
break;
}
mul[i]=mul[i-1]*(m-2-i+1)%mod;
}
}
int main(){
#ifdef DEBUG
freopen("ex_B1.in","r",stdin);
freopen("my.out","w",stdout);
#endif
sf("%d%d",&n,&m);
init();
dp[0]=1;
rep(i,0,n-1){
// pf("%lld\n",dp[i]);
add(dp[i+1],dp[i]*inv[n-i]%mod);
for(int k=0;i+k+1<=n;k++){
add(dp[i+k+1],dp[i]*mul[k]%mod*inv[n-i]%mod*ifac[k]%mod);
}
}
ll jc=1;
rep(i,1,n) jc=jc*i%mod;
ans=jc*dp[n]%mod;
pf("%lld\n",ans);
}