Description

Solution

令 $n=h+w$n=h+w

$1.O\left(n^2\right)$1.O(n2)

枚举行数 $i$i和列数 $j$j，
$P_h^i$Phi​代表 $h$h行里选了 $i$i行的排列（与顺序无关，所以是排列）
$P_w^j$Pwj​同理
但是两个排列只枚举了行与行和列与列之间的先后顺序，还不知道整个的先后顺序，那么再乘上一个 $C_{i+j}^i$Ci+ji​就得到了整个的方案数
$(i+1)(j+1)$(i+1)(j+1)为此时的贡献
很多人会以为这样就好了，但事实上因为过程中的答案统计的不一定只有一次，所以每个方案要乘上它接下来的方案个数 $P_{n-i-j}^{k-i-j}$Pn−i−jk−i−j​（ $i+j$i+j表示当前总操作次数， $k-i-j$k−i−j为剩下的操作次数），配张图：

这张图代表了答案的计算过程
我们发现 $1,2,3$1,2,3这三个点都经过了 $2$2次，要把这个东西统计进去
$ans=\sum _{i=0}^h\sum _{j=0}^w{P}_h^i{P}_w^j{C}_{i+j}^i(i+1)(j+1)P_{n-i-j}^{k-i-j}$ans=i=0∑h​j=0∑w​Phi​Pwj​Ci+ji​(i+1)(j+1)Pn−i−jk−i−j​

$2.O\left(nlogn\right)$2.O(nlogn)

把上式的 $ans$ans拆开来，得到：
$ans=\frac{h!w!(n-i-j)!(i+j)!(i+1)(j+1)}{i!j!(h-i)!(w-j)!n!}$ans=i!j!(h−i)!(w−j)!n!h!w!(n−i−j)!(i+j)!(i+1)(j+1)​
这东西可以用 $FFT$FFT优化

$3.O\left(logn\right)$3.O(logn)

考虑到我们要统计矩形的个数，那么只要统计左下角同时被行列两条线经过（边界的点默认已经被边界线经过）的个数即可
那么，在计算第 $i$i次分割的时候，不在边界上的点有 $\frac{C_i^2}{C_n^2}$Cn2​Ci2​​的概率被两条线切到（每次分割都会选怎么切，切到的两个数同时 $\le i$≤i的个数为 $C_i^2$Ci2​个，而切到数 $\le n$≤n的个数为 $C_n^2$Cn2​，所以概率为 $\frac{C_i^2}{C_n^2}$Cn2​Ci2​​）
而这样的点有 $hw$hw个，所以总数为 $\frac{(k-1)k(k+1)hw}{3n(n-1)}$3n(n−1)(k−1)k(k+1)hw​
对于在边界上，但不是左下角的点，概率为 $\frac{i}{n}$ni​总共 $n$n个，总数为 $\frac{k(k+1)}{2}$2k(k+1)​
左下角那个点每次概率为 $1$1， $k$k次后，总数为 $k$k
所以： $ans=\frac{(k-1)k(k+1)hw}{3n(n-1)}+\frac{k(k+1)}{2}+k$ans=3n(n−1)(k−1)k(k+1)hw​+2k(k+1)​+k

Code

过程中有 $0$0的话要特判掉

#include<bits/stdc++.h>
using namespace std;
const int M=1e9+7;
long long h,w,k;
int n;
int pw(int x,int y){
	int z=1;
	for (;y;y>>=1,x=1ll*x*x%M)
		if (y&1) z=1ll*z*x%M;
	return z;
}
int main(){
	scanf("%lld%lld%lld",&h,&w,&k);
	h%=M,w%=M,k%=M,n=(h+w)%M;
	printf("%lld",(1ll*k*(k+1)%M*(k-1)%M*((M+1)/3)%M*(h?h:1)%M*(w?w:1)%M*(n==1?1:pw(1ll*n*(n-1)%M,M-2))+1ll*k*(k+1)/2+k)%M);
}