#P6787. [2019福建夏令营]送分题

    ID: 6607 传统题 2000ms 128MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>难度分类省选/NOI-构造与建模对称性分析多项式与生成函数普通生成函数动态规划转移矩阵组合数学重复元素除重线性代数与代数行列式多项式对数导数积分转化有理生成函数线性递推生成函数求系数CF2900

[2019福建夏令营]送分题

送分题

题目描述

一个花钟由 2n2n 朵花构成,沿顺时针方向编号为 11 到 2n2n,每朵花使用 nn 种颜色中的一种。每种颜色恰好出现两次。

两朵花的距离为它们沿圆周两个方向之间较短的步数,即

d(u,v)=min⁡(∣u−v∣,2n−∣u−v∣).d(u,v)=\min(|u-v|,2n-|u-v|).

合法花钟需要满足:

  • 两朵同色花的距离不超过 22,或者恰好等于 nn。
  • 如果 u,vu,v 同色,那么 uu 的对面与 vv 的对面也同色。花 ii 对面的编号为 ((i+n−1) mod 2n)+1((i+n-1)\bmod2n)+1。

下图是一个 n=6n=6 的合法花钟。

n=6 的合法花钟,虚线连接同色花

花钟的美丽度定义如下:同时移除所有与自己对面的花同色的花,再把每两个相邻被移除位置之间剩下的花看成一个连续段,求所有连续段长度的乘积。连续段长度可以为 00;如果没有任何花被移除,则美丽度规定为 00。

例如,上图移除编号为 1,3,7,91,3,7,9 的花,得到四个连续段 {2}\{2\}、{4,5,6}\{4,5,6\}、{8}\{8\}、{10,11,12}\{10,11,12\},美丽度为 1×3×1×3=91\times3\times1\times3=9。

两个花钟本质不同,当且仅当存在一对位置 (u,v)(u,v),使这两个位置在一个花钟中同色,在另一个花钟中不同色。因此,只改变颜色名称不产生新的花钟;位置上的同色配对关系不同才算不同。

给定 nn,求所有本质不同的合法花钟的美丽度之和,对 998244353998244353 取模。

输入格式

一行一个整数 nn。

输出格式

输出一个整数,表示美丽度之和对 998244353998244353 取模的结果。

样例

下表每一行是一组独立样例,分别运行。

样例输入 样例输出
3 24
4
7 1316
15 3436404

数据范围与子任务

所有数据满足 1≤n≤500001\le n\le50000。

子任务 分值 附加限制
1 1010 n≤5n\le5
2 2020 n≤25n\le25
3 3030 n≤2000n\le2000
4 4040 无