#P4727. [HNOI2009] 图的同构计数

    ID: 4952 远端评测题 2000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>数学2009各省省选湖南群论置换Polya原理逆元

[HNOI2009] 图的同构计数

题目背景

当学生们遇到某个难题时经常会说“这怎么做,这不是NP问题吗?”、“这个只有搜了,这己经被证明是NP问题了”。但是,你应该淸楚,大多数人此时所说的NP问题其实都是指NPC问题。很多人没有真正掌握NP问题和NPC问题这两个基本概念。其实NP问题并不是那种“只有搜才行”的问题,NPC问题才是。

很久以前就有一个古老的传说:有―个著名的问题,即P是否等于NP的问题,传说中谁要是证明或者证伪了这个命题,他将获得幸福。这里P是指能在多项式时间里求解的问题的集合。而NP是指可在多项式时间里验证的问题的集合。显然P是NP的子集,因为能在多项式时间里求解的问题,必定可在多项式时间里验证。

到目前为止还没有人因这个命题得到幸福。但是,有一个总的趋势,也就是人们普遍认为,P=NPP=NP不成立,即,多数人相信,至少存在一个不可能有多项式时间复杂度的求解算法的NP问题。人们如此坚信PNPP \neq NP是有原因的,因为在研究NP问题的过程中找出了一类非常特殊的NP问题叫做NP-完全问题,也就是所谓的NPC问题。正是因为存在NPC问题,才使人们相信PNPP \neq NP

在提出NPC的概念之后,绝大多数“自然”的难题最后都被证明是NPC问题,只有三个例外,它们分别是:

  • 线形规划问题;
  • 图同构问题;
  • 素数判定问题与大数分解问题。

题目描述

小雪在了解到以上情况后,自认为直接挑战终极难题还有不少困难,于是决定先从简单的问题做起,具体来说,他对图同构问题产生了浓厚的兴趣。AA图与BB图被认为是同构的是指:AA图的顶点经过一定的重新标号以后,AA图的顶点集和边集要完全与BB图一一对应。

小雪现在专注于如何判断两个图是否同构,同时他还想知道两两互不同构的含NN个点的图有多少种。众所周知含NN个点的简单图最多有N(N1)/2N*(N-1)/2条边,这样含NN个点的图有2N(N1)/22^{N*(N-1)/2}种可能的情况。显然这些图中有很多图是同构的,小雪想知道的便是:若同构的图算成一种,则有多少种不同的图。他把这个任务丢给了你,在他想出来之前快点解决吧!

输入格式

从文件input.txt中读入数据,文件中只有一个非负整数NN,表示图的顶点数,且0N600 \leq N \leq 60

输出格式

输出文件output.txt中仅包含一个整数,表示含NN个点的图在同构意义下不同构的图的数目。因为答案可能很大,所以输出的最终答案是mod997\bmod 997的结果(997997是一个素数)。

1
1
2
2
3
4
5
34
9
493

提示

对于 40%40 \% 的数据,N20N \le 20
对于 100%100 \% 的数据,0N600 \le N \le 60