原题链接
\(该题运用到了杨表的知识 发该篇题解是为了加深对于杨表的理解\)
\(发表该篇题解仅用于个人理解 感觉洛谷上的题解更好\)
洛谷题解传送门
\(杨氏矩阵(Young tableau)，又名杨表，是一种常用于表示论和舒伯特演算中的组合对象。\)
\(杨表是一种特殊的矩阵。它便于对称群和一般线性群的群表示和性质研究。\)
\(杨表由剑桥大学数学家阿尔弗雷德·杨（Alfred Young）于 1900 年首次提出，于 1903 年被德国数学家弗罗贝尼乌斯（Ferdinand Georg Frobenius）应用于对称群的研究。\)
\(杨表有一个基础的概念\)
\(对于1-n的元素填充 它的各行各列都得满足递增\)
\(臂长：对于每个单元格向右的元素个数（不包含自己）\)
\(腿长：对于每个单元格向下的元素个数（不包含自己）\)
\(勾长：对于每个单元格的臂长+腿长加一（即向右元素个数+向下元素个数+自己）\)
\(性质：\)
\(第一行的长度为该序列的LIS长度\)
\(第一列的长度为该序列的LDS长度\)
\(一个确定的序列可以生成两张杨表 一张记录其第一次插入的顺序 一张记录其形成的标准杨表\)
\(code:\)
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define pii pair<int,int>
using namespace std;
//const int mod=998244353;
int mod;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int qpw(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 inv(int x){return qpw(x,mod-2);}
const int N=2e5+10;
int f[N],deg[N],siz[N];
vector<int>G[N];
int find(int x){
return f[x]==x?x:f[x]=find(f[x]);
}
void dfs1(int x,int fa){
for(int son:G[x]){
if(son==fa)continue;
dfs1(son,x);
if(deg[x]==2&°[son]==3){
siz[find(son)]++;
}else if(deg[son]==2&°[x]==3){
siz[find(x)]++;
}else if(deg[son]==3&°[x]==3){
siz[find(x)]+=siz[find(son)];
f[find(son)]=find(x);
}
}
}
void solve(){
int n,m;cin>>n>>m>>mod;
int ans=1;
for(int i=1;i<=n*m;i++)ans=ans*i%mod;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ans=ans*inv(i+j-1)%mod;
}
}
map<vector<int>,int>dp;
vector<int>ve;
for(int i=1;i<=m;i++)ve.pb(0);
dp[ve]=1;
for(int k=1;k<=n*m;k++){
map<vector<int>,int>ndp;
for(auto x:dp){
auto v=x.first;
auto val=x.second;
for(int i=0;i<m;i++){
if(v[i]<n&&(i==0||v[i]<v[i-1])){
if(i!=m-1&&v[i]==n-1&&v[i+1]<n-1)continue;
++v[i];
ndp[v]=(ndp[v]+val)%mod;
--v[i];
}
}
}
swap(dp,ndp);
}
for(int i=0;i<m;i++)ve[i]=n;
ans=ans*dp[ve]%mod;
cout<<ans;
}
signed main(){
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int _=1;
// cin>>_;
while(_--)solve();
}