2023-01-08

题目传送门

翻译

难度&重要性(1~10):1

题目来源

AtCoder

题目算法

dp,逆元

解题思路

转化一下，分离行列，针对每一对去计算方案。

以下以行为例子。

考虑两个之间行距为 \(i\)，都可以随便选择一列，从 \(n-i\) 个行距为 \(i\) 的行组合中挑选一个，然后再选择剩余 \(k-2\) 个，方案数就是 \(i\times(n-i)\times m^2\times\dbinom{nm-2}{k-2}\)。

加起来即可，复杂度 \(O(n+m)\)。

完成状态

已完成

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll Maxn=1e6+7,Mod=1e9+7,p=1e9+7;
ll n,m,k,ans,fac[Maxn];
inline ll ksm(ll a,ll b,ll mod){
	ll z=1;while(b){if(b&1)z=z*a%mod;a=a*a%mod;b>>=1;}return z;
}
inline ll inv(ll a,ll mod){
	return ksm(a,mod-2,mod);
}
inline ll C(ll a,ll b){
	if(b>a) return 0;
	return fac[a]*inv(fac[b],p)%p*inv(fac[a-b],p)%p;
}
inline ll Lucas(ll n,ll m){
    return C(n,m)%p;
}                                                    
int main(){
	scanf("%lld%lld%lld",&n,&m,&k);fac[0]=1;
	for(ll i=1;i<=Maxn-7;i++) fac[i]=fac[i-1]*i%Mod;
	for(ll i=1;i<=n;i++)
		for(ll j=1;j<=m;j++){
			ans+=(n-i+1)%Mod*(n-i)%Mod*m*inv(2,p)%Mod+(m-j+1)*(m-j)%Mod*(n-i+1)%Mod*inv(2,p)+j*(j-1)%Mod*(n-i)%Mod*inv(2,p)%Mod;
			ans%=Mod;ans=(ans+Mod)%Mod;
		}
	ans=(ans%Mod*Lucas(n*m,k)%Mod*Lucas(k,2)%Mod*inv(Lucas(n*m,2),p)%Mod+Mod)%Mod;	
	printf("%lld",ans);
	return 0;
}