自共轭Ferrers图

   

  ●问题描述

  整数的拆分问题是组合数学中的一个基本问题。一个整数的拆分是指把这个整数分成若干个与次序无关的正整数之和。在人们研究整数拆分问题时,为了形象直观地帮助人们的思维,可以用Ferrers图来表示。

  Ferrers图是一个自上而下的n层格子,且上层格子数不少于下层格子数。

             
                   图一

  如图一所示,图中的虚线称为Ferrers图的虚轴。若将图一绕虚轴旋转180°,即将第一行与第一列对调,将第二行与第二列对调,……,这样所得到的图仍为Ferrers图,如图二所示。

               
                   图二

  这两个图称为一对共轭Ferrers图。有一些Ferrers图,沿虚轴转换后的Ferrers图仍为它本身,也就是说这个Ferrers图关于虚轴对称,那么这个Ferrers图称为自共轭Ferrers图。本题中的图三便是一个自共轭Ferrers图。

  在组合数学中,一个含有n个格子的Ferrers图对应一个n的拆分。在本题中,我们称含有n个格子的Ferrers图的大小为n。例如把6拆分成三个整数3、2、1之和即6=3+2+1,对应的Ferrers图的第一行有3个格子,第二行有2个格子,第三行有1个格子(如图三所示)。这个Ferrers图的大小为6。

              
                    图三

  由于一个整数n拆分成若干个整数之和的拆分方法数是不一定的,所以说一个大小为n的Ferrers图的数量也是不确定的。现在我们需要寻找的是大小为n的自共轭Ferrers图的总数。

  ●数据输入:输入数据由文件ferrers.in提供,文件中有一个整数n(1≤n ≤300)

  ●结果输出:将结果输出到文件ferrers.out中。如果存在大小为n的自共轭Ferrers图,则输出大小为n的自共轭Ferrers图的总数;若不存在大小为n的自共轭Ferrers图,则输出"NO ANSWER"。

  ●输入输出样例

输入样例 输出样例
ferrers.in ferrers.out
6 1


 
 
网站导航 | 关于曙光 | 联系我们 | 请提意见
Copyright © FuJian Sunshine Educational Info. Co.,Ltd.
福建曙光教育资讯有限公司 版权所有