#P6787. [2019福建夏令营]送分题
[2019福建夏令营]送分题
送分题
题目描述
一个花钟由 朵花构成,沿顺时针方向编号为 到 ,每朵花使用 种颜色中的一种。每种颜色恰好出现两次。
两朵花的距离为它们沿圆周两个方向之间较短的步数,即
合法花钟需要满足:
- 两朵同色花的距离不超过 ,或者恰好等于 。
- 如果 同色,那么 的对面与 的对面也同色。花 对面的编号为 。
下图是一个 的合法花钟。

花钟的美丽度定义如下:同时移除所有与自己对面的花同色的花,再把每两个相邻被移除位置之间剩下的花看成一个连续段,求所有连续段长度的乘积。连续段长度可以为 ;如果没有任何花被移除,则美丽度规定为 。
例如,上图移除编号为 的花,得到四个连续段 、、、,美丽度为 。
两个花钟本质不同,当且仅当存在一对位置 ,使这两个位置在一个花钟中同色,在另一个花钟中不同色。因此,只改变颜色名称不产生新的花钟;位置上的同色配对关系不同才算不同。
给定 ,求所有本质不同的合法花钟的美丽度之和,对 取模。
输入格式
一行一个整数 。
输出格式
输出一个整数,表示美丽度之和对 取模的结果。
样例
下表每一行是一组独立样例,分别运行。
| 样例输入 | 样例输出 |
|---|---|
| 3 | 24 |
| 4 | |
| 7 | 1316 |
| 15 | 3436404 |
数据范围与子任务
所有数据满足 。
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | ||
| 2 | ||
| 3 | ||
| 4 | 无 |