深巢温泉

$\color{deeppink}link$ $\Delta$

转化题意为求期望。

考虑对于一个位置 $i$，求出他所有的 $x$ 的期望贡献。

但是，若直接来表示当前是否为 $x$ 有些难做，因为取 $\min$ 和 $\max$ 时都无法确定是否变为该值，故用 $0/1$ 代表当前数是否大于等于 $x$。

当贡献为 $1$ 时，直接加入答案，因为对于 $x$，加进答案的 $1$ 就有小于等于 $x$ 的 $x$ 个。

枚举 $i,x$。

注意到只有对 $1$ 取 $\max$ 和对 $0$ 取 $\min$ 是有用的。

用 $a$ 表示前者的概率，$b$ 表示后者的概率，$c$ 表示查询包含 $i$ 的概率，用 $tot$ 代表可选的操作总数。

$tot=\frac{n(n+1)}{2}\times (2m+1)\\ a=\frac{i\times (n-i+1)}{tot}\times (m-x)\\ b=\frac{i\times (n-i+1)}{tot}\times (x-1)\\ c=\frac{i\times (n-i+1)}{tot}$

做完长度为 $q$ 的操作序后贡献为 $1$ 的期望是 $\sum\limits_{i=0}^{q-1}\dfrac{ac}{a+b}(1-(1-a-b)^i)$。

还要考虑 $x$ 对答案的影响。

发现对于相同的位置 $i$，$a+b$ 总是 $\dfrac{i\times (n-i+1)}{tot}\times (m-1)$，故将 $\dfrac{c}{a+b}$ 移出去，然后对于每一个 $x$，后面的等比数列总是相同的，故可以求出 $sum_a$，将其乘上等比数列的和即可。

最后还要注意 $ans$ 是期望，还要乘上总操作数 $tot^q$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7,N=2e5+50;

int inv,n,m,q,tot,S,ans,inv2=(mod+1)/2;

int ksm(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;b>>=1;
	}
	return ans;
}

int get_sum(int a,int t)
{
	if(a==1)return t;
	return (1-ksm(a,t)+mod)*ksm(1-a+mod,mod-2)%mod;
}

main()
{
	cin>>n>>m>>q;
	tot=n*(n+1)%mod*inv2%mod*(2*m+1)%mod,inv=ksm(tot,mod-2);
	S=m*(m-1)%mod*inv2%mod;
	for(int i=1;i<=n;i++)
	{
		int a_and_b=i*(n-i+1)%mod*inv%mod*m%mod;
		int val=(q-get_sum(1-a_and_b+mod,q)+mod)%mod*ksm(a_and_b,mod-2)%mod;
		int c=i*(n-i+1)%mod*inv%mod;
		int suma=i*(n-i+1)%mod*S%mod*inv%mod;
		ans=(ans+c*suma%mod*val%mod)%mod;
	}
	cout<<ans*ksm(tot,q)%mod;
}