首页 > 其他 > 详细

杨氏矩阵与勾长公式

时间:2019-10-06 21:59:26      阅读:61      评论:0      收藏:0      [点我收藏+]

杨氏矩阵又叫杨氏图表,它是这样一个矩阵,满足条件:

(1)如果格子(i,j)没有元素,则它右边和上边的相邻格子也一定没有元素。 
(2)如果格子(i,j)有元素a[i][j],则它右边和上边的相邻格子要么没有元素,要么有元素且比a[i][j]大。

勾长公式。

对于给定形状,不同的杨氏矩阵的个数为:n!/(每个格子的钩子长度加1的积)。 
其中钩子长度定义为该格子右边的格子数和它上边的格子数之和。

然后看看ACwing这题

https://www.acwing.com/problem/content/273/

代码如下

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll tmp[110],num[110];
int main()
{
    int n;
    while(cin>>n&&n)
    {
        memset(tmp,0,sizeof(tmp));
        for(int i=1;i<=n;i++)
        {
            cin>>num[i];
        }
        ll tot=0,t1=1,t2=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=num[i];j++)
            {
                tmp[++tot]+=num[i]-j+1;
                for(int k=i+1;k<=n;k++)
                {
                    tmp[tot]+=(num[k]>=j);
                }
            }
        }
        ll p;
        for(int i=1;i<=tot;i++)
        {
            t1*=i;
            t2*=tmp[i];
            p=__gcd(t1,t2);
            t1/=p;
            t2/=p;
        }
        cout<<t1/t2<<"\n";
    }
    return 0;
}

 

杨氏矩阵与勾长公式

原文:https://www.cnblogs.com/hh13579/p/11628501.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!