数学赛高!
题解
这题其实可以不用dp解法,直接用数学方法(杨辉矩阵和勾长公式)即可
前置科普:
杨氏矩阵又叫杨氏图表,它是这样一个矩阵,满足条件:
如果格子 (i,j) 没有元素,则它右边和上边的相邻格子也一定没有元素。
如果格子 (i,j) 有元素a_{i,j},则它右边和上边的相邻格子要么没有元素,要么有元素且比a_{i,j}大。
下面介绍一个公式,那就是著名的勾长公式(钩子公式)。
对于给定形状,不同的杨氏矩阵的个数为:n!除以每个格子的钩子长度\bold{+1}的积。
其中钩子长度定义为该格子右边的格子数和它上边的格子数之和。
例: 给四行,第一行放5个数字,第二行放3个数字,第三行放3个数字,第四行放1个数字,都是左对齐的排列。现有1~12共12个数字,要求放到这四行中,从上到下,从左到右都是按小到大排列,问你共有几种排法?
摆的样子如下:
#####
###
###
#
乍一看不是杨辉矩阵,其实再一看它不过是一个上下翻折了的杨辉矩阵,即在上面的定义中把右边和上边
变成右边和下边
所以这个问题直接利用钩子公式解决即可,钩子定义也变成该格子右边的格子数和它下边的格子数之和
。
共有12个数字,12!=479001600
然后易得每个钩子的长度如下:
75400
421
310
0
答案即为479001600/(7+1)/(5+1)/(4+1)/(0+1)/(0+1)/(4+1)/(2+1)/(1+1)/(3+1)/(1+1)/(0+1)/(0+1)=8316种排法
那么这道题目明显就是这道简单数学题的进化版了
直接膜你即可,但是我懒得构建二维数组了
其实根据钩子的定义,对于一个数a_{i,j}(在第a_{i}行,该行有p_{i}个数,下标从0开始)
那么右边的格子数即为p_{i}-j-1
下边的格子数的话,直接往下枚举,若枚举到的那行的元素个数\gt{j},则a_{i,j}下面在这一行有格子
这里可以有个小优化,由这个杨辉矩阵的定义易得,若一个格子为空,那么下面的所有格子都为空
所以枚举的时候如果不符合条件,就直接break
跳出循环
然后得到的格子数按上面的公式做即可
注意: 多组数据
代码
因为笔者很懒(ruo
),所以直接写了一个很烂的python
代码
import math # 引用python阶乘库
a=[0]*10 # 存储每行人数的数组
while(1): # 多组数据
k=int(input())
if(k==0): # 结束标志(行数为0)
break
s=[int(i) for i in input().split()]
n=0
for i in range(0,k):
a[i]=s[i] # 获取每排人数
n+=a[i] # 累加总人数
p=math.factorial(n) # 公式中n!
for i in range(0,k):
for j in range(0,a[i]): # 每一个元素枚举膜你
t=a[i]-j-1 # t为钩子长度的计数器,初值如上
for l in range(i+1,k): # 如上向下循环枚举
if(a[l]>j): # 如上,若这行长度大于j则计数器+1
t+=1
else: # 上面提到的优化
break
p//=t+1 # 除以钩子长度+1,注意"//"是整除
print(p) # 输出答案p