题解 P2132 【小Z的队伍排列】

X_yea · 2019-06-30 20:34:53 · 题解

DP解法各位大佬已经说的够详细了

这里就说一下本题的数学解法吧qwq~

数学方法题解

杨氏矩阵

这些就是杨氏矩阵(允许我偷个懒）

我们发现她有如下性质：

• 如果格子(i,j)没有元素，则它右边和下边的相邻格子也一定没有元素。

• 如果格子(i,j)有元素a[i][j]，则它右边和下边的相邻格子要么没有元素，要么有元素且比a[i][j]大。

钩子长度

定义：该格子右边的格子数和它下边的格子数之和。

例如k=3，n=6，每排人数分别为3，2，1时，每个格子的钩子长度如图所示：

钩子公式

对于给定形状，不同的杨氏矩阵的个数为：n！除以每个格子的钩子长度加1的积。

例如上图的不同的杨氏矩阵的个数=6！/(5 3 1 3 1 * 1)=16

CODE

#include <bits/stdc++.h>
#define int long long//记得开long long
using namespace std;

int k,n,a=1,b=1,c,cnt,sum[31],line[6];

int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}

signed main()
{
    cin>>k;
    for(int i=1; i<=k; i++)
    {
        cin>>line[i];
        n+=line[i];
    }
    for(int i=1; i<=k; i++)
    {
        for(int j=1; j<=line[i]; j++)
        {
            int hook=line[i]-j+1;
            for(int k=i+1; k<=n; k++)
            {
                if(line[k]>=j)
                    hook++;
                else break;
            }
            sum[++cnt]=hook;
        }
    }
    for(int i=1; i<=n; i++)//这里是约分，防止溢出
    {
        a*=i;
        b*=sum[i];
        c=gcd(a,b);
        if(c!=1)
        {
            a/=c;
            b/=c;
        }
    }
    cout<<a/b;
    return 0;
}