Great Cells ＆ Counting Grids

101194 H Great Cells

The question ：
If a lattice in a matrix satisfies that it is strictly greater than all the other numbers of its rows and columns , Then we call this lattice Great Cells,$A_g$ The representative happens to have $g$ individual Great Cells When the number of programs . Give a $n$ That's ok $m$ Matrix and a number of columns $k$,$k$ Indicates that each grid can be selected from $[1,k]$ Select a number from the list and put it into the current grid .($N,M,K<=200$)
To calculate the result of this formula :
$$\sum _{g=0}^{NM}(g+1)\cdot A_g\mathrm{m}\mathrm{o}\mathrm{d}(1e9+7)$$

Ideas ：
Deform the required formula appropriately to get ：
$$\sum _{g=0}^{NM}g\cdot A_g\mathrm{m}\mathrm{o}\mathrm{d}(1e9+7)+\sum _{g=0}^{NM}{A}_g\mathrm{m}\mathrm{o}\mathrm{d}(1e9+7)$$

It is not difficult to find that the formula on the right is to sum all the schemes , So for $K^{NM}$;
Next, look at the formula on the left , For a particular one $g$ individual Great Cells The plan , The contribution to the overall answer is $g$, It can be seen as every Great Cells All contribute to the total answer 1; So the formula on the left can be seen as , For all grids as Great Cells Sum of cases .
Then just for each grid , Find out what he does Great Cells The number of schemes is enough , Just satisfy that it is a peer 、 The maximum value in the same column , You can enumerate the values of this lattice , Come and make peace ：
$$NM\sum _{i=1}^K(i-1{)}^{N+M-2}\cdot K^{NM-N-M+1}$$
Finally, add $K^{NM}$ that will do ;

Code ：

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
#define ll long long

const ll mod=1e9+7;
int t,n;
ll qp(ll x,ll n){
    
	ll ans=1;
	while(n){
    
		if(n&1)ans=ans*x%mod;
		x=x*x%mod;
		n/=2; 
	}
	return ans;
}

int main(){
    
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>t;
	int T=0;
	while(t--){
    
		T++;
		int n,m,k;
		cin>>n>>m>>k;
		ll ans=qp(k,n*m);
		ll res=0;
		for(int i=1;i<k;i++){
    
			res=(res+qp(i,n-1+m-1)*qp(k,n*m-n-m+1)%mod)%mod;
		}
		res=res*n*m%mod;
		ans=(ans+res)%mod;
		cout<<"Case #"<<T<<": "<<ans<<'\n'; 
	}
	return 0;
}
/* */

ARC143 B Counting Grids

The question ：
Seek to use $1$ To $N^2$ fill $N\ast N$ How many schemes does the matrix have , There is no point of satisfaction , It is both the maximum value of the same column and the minimum value of the same row .
Ideas ：
We weigh a point , If it is both the maximum value of the same column and the minimum value of the same row , So it's a bad point ;
Then you need to ask The number of schemes without bad points , It's not hard to think of using tolerance and exclusion ：
hypothesis $a_{i,j}$ Express $(i,j)$ This point is bad ;
In fact, we need to ask
$$|S-a_{1,1}\cup a_{1,2}\cup ...\cup a_{n,n}|$$
Expand with the principle of inclusion and exclusion , hypothesis $f(i)$ For at least $i$ The number of schemes where a point is a bad point ：
$$=|S|-C_{N\ast N}^1\cdot f(1)+C_{N\ast N}^2\cdot f(2)-....C_{N\ast N}^{N\ast N}\cdot f(N\ast N)$$

If we ask $f(i)$ Words , For each $f(i)$, I can only think of highly complex $dp$ How to find , The complexity is definitely unbearable .

But this topic also has a wonderful property ： It is impossible to have more than one bad point , Prove the following ：

hypothesis $a,d$ For the bad , Then according to the definition of bad points , You can get the following relation ：
$a>c$、$a<b$、$d>b$、$d<c$ ;
Put it in order ：$a<b<d$、$a>c>d$ ;

It's obviously a conflict , that $\forall x\in [2,N\ast N],f(x)=0$ ;
Then the original formula becomes ：
$$=|S|-C_{N\ast N}^1\cdot f(1)$$
Easy to get ：$|S|=(N\ast N)!$
Then you need to ask $f(1)$, It only needs to satisfy that there is a point satisfying that it is the maximum value of the same column , At the same time, it is also the minimum value of peers , It's not hard to figure out ：
$$f(1)=N\ast N\ast C_{N^2}^{2N-1}\cdot (N-1)!(N-1)!(N\ast N-2N+1)!$$

Code ：

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
#define ll long long

const ll mod=998244353;
int t,n;
ll qp(ll x,ll n){
    
	ll ans=1;
	while(n){
    
		if(n&1)ans=ans*x%mod;
		x=x*x%mod;
		n/=2; 
	}
	return ans;
}
ll jie[250005];
ll inv[250005];
int main(){
    
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
	ll ans=0;
	jie[0]=1;
	for(int i=1;i<=n*n;i++)jie[i]=jie[i-1]*i%mod;
	inv[n*n]=qp(jie[n*n],mod-2);
	for(int i=n*n;i>=1;i--)inv[i-1]=inv[i]*i%mod;
	ans=n*n*jie[n*n]%mod*inv[n*n-2*n+1]%mod*inv[2*n-1]%mod*jie[n-1]%mod*jie[n-1]%mod*jie[n*n-2*n+1]%mod;
	ans=(jie[n*n]-ans+mod)%mod;
	cout<<ans<<'\n';
	
	return 0;
}
/* */