很好的一题，做的时候没有一点思路，看了题解。看来做过的题目还是太少了，记录一下经验。
注意到 $1\le N\le2\times 10^5$ 和 $1\le M \le 10^9$，如此庞大的数据，dp 是肯定不行的。
当字典序 $A<B$ 时，当且仅当存在 $i$，使得 $\forall x \in [1,i)$，$A_x=B_x$ 且 $A_i<B_i$。那么我们对于 $\forall i \in [1,n]$ 的答案求和即可。
先考虑当 $i=1$ 时如何计算答案。首先 $i=P_i$ 时答案为 $0$；$i\neq P_i$ 时，除了这两位其它都能随便选，方案数为 $m^{n-2}$。当第 $i$ 位为 $x$ 时，第 $P_i$ 位能选 $[1,x)$ 的所有数，所以方案数为 $\frac{m(m-1)}{2}$。根据乘法原理，总方案数为 $m^{n-2}\times \frac{m(m-1)}{2}=\frac{m^{n-1}\times (m-1)}{2}$。
现在把 $i$ 推广，因为 $\forall x \in [1,i)$，$A_x=A_{P_x}$，所以可以用并查集将 $x$ 和 $P_x$ 连通，对于在同一个连通块中的点，它们的值时相同的。那么方案数即为 $\frac{m^{cnt-1}\times (m-1)}{2}$，其中 $cnt$ 为连通块个数。
代码并不难打，注意分母的 $2$ 要用逆元即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,mod=998244353;
int n,m,cnt,ans;
int a[N],f[N];
int find(int k)
{
return f[k]==k?k:f[k]=find(f[k]);
}
int qpow(int x,int y)
{
int ans=1;
while(y)
{
if(y%2)ans*=x,ans%=mod;
x*=x,x%=mod,y/=2;
}
return ans;
}
signed main()
{
const int k=qpow(2,mod-2);
cin>>n>>m;
cnt=n;
for(int i=1;i<=n;i++)
cin>>a[i],f[i]=i;
for(int i=1;i<=n;i++)
{
int x=find(i),y=find(a[i]);
if(x==y)continue;
ans+=qpow(m,cnt-1)*(m-1)%mod*k%mod;
ans%=mod;
f[x]=y,cnt--;
}
cout<<ans;
return 0;
}