AT_arc114_c

提供一个更臭一点的 $O(n)$ 做法。

首先分析，如果现在已知 $A$，怎么求 $f(A)$。首先贪心地想，设依次操作 $v_i$，若 $v_{i+1}<v_i$，那么换成先操作 $v_i$ 再 $v_{i+1}$ 一定不劣，因为可能的结果后者包含前者。于是一定是按 $v$ 从小到大操作。

然后发现，对于一个 $a_i=a_j=x$，若 $\exists k\in(i,j),a_k<x$，则无法用一次操作同时使 $a_i,a_j$ 满足要求，否则会影响中间已经确定的数。同时，若 $a_i$ 这个数是第一次出现，显然也要一次操作。

然后拆开算贡献。对于第一种情况，考虑枚举 $a_i=k$ 上一次出现的位置为 $j$，则 $(i,j,k)$ 产生贡献的要求有：$(i,j)$ 中没有 $k$ 且 $\exists p\in(i,j),a_p<k$。计算方案数，考虑算没有 $k$ 的方案减去全 $>k$ 的方案，为 $((m-1)^{i-j-1}-(m-k)^{i-j-1})m^{n-i+j-1}$，后面的 $m$ 是其他位置任取的方案数。于是方案数为：

$\sum\limits_{i=1}^n\sum\limits_{k=1}^m\sum\limits_{j=1}^{i-1}((m-1)^{i-j-1}-(m-k)^{i-j-1})m^{(n-(i-j+1))}$

然后推式子。发现只和 $i-j$ 有关：

$=\sum\limits_{i=1}^{n-1}\sum\limits_{k=1}^m((m-1)^{i-1}-(m-k)^{i-1})(n-i)m^{n-i-1}$

改变枚举顺序。

$=\sum\limits_{k=1}^m\sum\limits_{i=1}^{n-1}((m-1)^{i-1}(n-i)m^{n-i-1}-(m-k)^{i-1}(n-i)m^{n-i-1})$

对于 $x^iy^{n-i}$ 状物，有个 trick 是提出来 $y^n$ 变成 $y^n(\frac xy)^i$。

$=m^{n-2}\sum\limits_{k=1}^m\sum\limits_{i=1}^{n-1}((\frac{m-1}{m})^{i-1}(n-i)-(\frac{m-k}{m})^{i-1}(n-i))$

$=m^{n-2}(n\sum\limits_{k=1}^m\sum\limits_{i=1}^{n-1}((\frac{m-1}{m})^{i-1}-(\frac{m-k}{m})^{i-1})-\sum\limits_{k=1}^m\sum\limits_{i=1}^{n-1}(i(\frac{m-1}{m})^{i-1}-i(\frac{m-k}{m})^{i-1}))$

发现前半部分是等比数列形式，可以 $O(1)$ 算。后半形似 $\sum (i+1)x^i$，对于这种的处理，令 $A=\sum\limits_{i=0}^n (i+1)x^i,xA=\sum\limits_{i=1}^{n+1} ix^i$，相减得 $(x-1)A=(n+1)x^{n+1}-\sum\limits_{i=0}^nx^i$，结合等比数列也是 $O(1)$。

于是 令 $f(x,n)=\sum\limits_{i=0}^nx^i=\frac{x^{n+1}-1}{x-1},g(x,n)=\sum\limits_{i=0}^{n}(i+1)x^i=\frac{(n+1)x^{n+1}-f(x,n)}{x-1}$，则有：

$=m^{n-2}(n\sum\limits_{k=1}^m(f(\frac{m-1}{m},n-2)-f(\frac{m-k}{m},n-2))-\sum\limits_{k=1}^m(g(\frac{m-1}{m},n-2)-g(\frac{m-k}{m},m-2)))$

此时 $O(n\log n)$ 已经是简单的，至于 $O(n)$，容易发现需要快速幂的只有 $x^{n-1}$，线性筛预处理，再预处理一些逆元即可。

后面部分的式子比较简单，为 $\sum\limits_{i=1}^n\sum\limits_{k=1}^m(m-1)^{i-1}m^{n-i}$。容易发现与 $k$ 无关，于是动态维护后面两个东西即可。

code：

int n,m,s,pm[N],pw[N],inv[N];
int ivm,ivmp;
bool vis[N];
il int Mod(int x,int y){
	return x+y>=mod?x+y-mod:x+y;
}
il int qpow(int x,int y){
	int ret=1;
	while(y){
		if(y&1){
			ret=1ll*ret*x%mod;
		}
		x=1ll*x*x%mod,y>>=1;
	}
	return ret;
}
il int F(int x){
	return mod-1ll*Mod(1ll*pw[x]*ivmp%mod,mod-1)*m%mod*inv[m-x]%mod;
}
il int G(int x){
	return mod-1ll*Mod(1ll*(n-1)*pw[x]%mod*ivmp%mod,mod-F(x))*m%mod*inv[m-x]%mod;
}
void Yorushika(){
	read(n,m);
	if(n==1){
		printf("%d\n",m);
		return;
	}
	pw[1]=inv[1]=1;
	rep(i,2,m){
		inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
		if(!vis[i]){
			pm[++s]=i;
			pw[i]=qpow(i,n-1);
		}
		rep(j,1,s){
			if(pm[j]>m/i){
				break;
			}
			vis[i*pm[j]]=1;
			pw[i*pm[j]]=1ll*pw[i]*pw[pm[j]]%mod;
			if(i%pm[j]==0){
				break;
			}
		}
	}
	ivm=qpow(m,mod-2),ivmp=qpow(ivm,n-1);
	int ans=0;
	rep(k,1,m){
		ans=Mod(ans,1ll*n*Mod(F(m-1),mod-F(m-k))%mod);
		ans=Mod(ans,mod-Mod(G(m-1),mod-G(m-k)));
	}
	ans=1ll*ans*qpow(m,n-2)%mod;
	int x=1,y=qpow(m,n-1);
	rep(i,1,n){
		ans=Mod(ans,1ll*x*y%mod*m%mod);
		x=1ll*x*(m-1)%mod,y=1ll*y*inv[m]%mod;
	}
	printf("%d\n",ans);
}
signed main(){
	int t=1;
	//read(t);
	while(t--){
		Yorushika();
	}
}

吐槽一下，这种题明明可以出到 $n=10^7$ 结果偏偏出了 $n=5000$，直接变成了zz题了……