[HNOI2001] 棋盘变换
题目描述
一个 $n\times n$ 的棋盘,在其中填入 $1$ 和 $-1$。经过一次变换后,方格里的每个数将会变成变换之前与之相邻的四个数的积。例如:
![](https://cdn.luogu.com.cn/upload/image_hosting/2q4jbad8.png)
但有一些状态,变换前和变换后是一样的,例如全部是 $1$ 的状态。这种状态被称为不变状态。
你的任务是要找到所有本质不同的不变状态(旋转或翻转之后的状态被视为是本质上相同的)。
输入输出格式
输入格式
一行一个正整数 $n$。
输出格式
一行一个正整数表示所有本质不同的方案数。
输入输出样例
输入样例 #1
4
输出样例 #1
5
说明
$1\le n\le 30$。
题目给出范围内,不变状态总数 $<9\times 10^3$。