-
发现答案至少是不同 \(A _ i\) 的个数。
-
两个相同的 \(A _ i\) 会在不同的操作中被赋值，当且仅当中间有一个比 \(A _ i\) 小的数。
第一部分的答案为 \(m (m ^ n - (m - 1) ^ n)\)，也就是对于每个值，令所有情况减去其没有出现的情况。
第二部分需要枚举相同的 \(A _ i = x\)，和它们位置中间的数的个数 \(y\)。为避免算重，这 \(y\) 个数不能是 \(x\)，再容斥掉这 \(y\) 个数中没有 \(< x\) 的数的情况，对答案的贡献为 \(f (x, y) = ((m - 1) ^ y - (m - x) ^ y) \times m ^ {n - (y + 2)}\)。所以第二部分的答案为 \(\displaystyle \sum _ {x = 2} ^ n \sum _ {y = 1} ^ {n - 2} (n - y - 1) \times f (x, y)\)。
时间复杂度 \(\text O (nm)\)。
#include<cstdio>
#define N 5005
using namespace std;const int mod=998244353;
int n,m,ans,pw[N][N];
int main() {scanf("%d%d",&n,&m);for(int i=0;i<=m;i++) {pw[i][0]=1;for(int j=1;j<=n;j++) pw[i][j]=1ll*pw[i][j-1]*i%mod;}ans=1ll*(pw[m][n]-pw[m-1][n])*m%mod;for(int i=2;i<=m;i++)for(int j=1;j<=n-2;j++)ans=(ans+1ll*(n-j-1)*(pw[m-1][j]-pw[m-i][j])%mod*pw[m][n-j-2])%mod;printf("%d\n",ans);return 0;
}