#P2225. [HNOI2001] 棋盘变换

    ID: 1241 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划dp2001各省省选湖南最大流费用流

[HNOI2001] 棋盘变换

题目描述

一个 n×nn\times n 的棋盘,在其中填入 111-1。经过一次变换后,方格里的每个数将会变成变换之前与之相邻的四个数的积。例如:

但有一些状态,变换前和变换后是一样的,例如全部是 11 的状态。这种状态被称为不变状态。

你的任务是要找到所有本质不同的不变状态(旋转或翻转之后的状态被视为是本质上相同的)。

输入格式

一行一个正整数 nn

输出格式

一行一个正整数表示所有本质不同的方案数。

4
5

提示

1n301\le n\le 30

题目给出范围内,不变状态总数 <9×103<9\times 10^3