#P11483. [2023省队模拟]写题

    ID: 10631 传统题 1500ms 512MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2500提高+/省选-自相似递归结构线性递推二次剩余模逆元费马小定理快速幂快速乘防溢出

[2023省队模拟]写题

题目描述

星鼻鼹鼠部落的横截面是一条 nn 阶 CCF 曲线。把曲线的各条单位线段视为墙,在曲线范围内,从上方开口可以沿没有墙阻挡的相邻方格到达的方格称为中空方格。

最上面一行的所有中空方格都会被水填满。水可以穿过没有墙阻挡的格边,从已经填满的中空方格流向它的左边、右边或下边的中空方格。

求最终被水填满的方格数,对质数 92233720368547757839223372036854775783 取模。

CCF 曲线

记 ii 阶 CCF 曲线为 HiH_i。H1H_1 由单位正方形的左边、下边、右边组成,上边留作开口。

由 HiH_i 构造 Hi+1H_{i+1} 时,将 HiH_i 复制为四份,按 2×22\times2 排列。左上角的一份逆时针旋转 90∘90^\circ,右上角的一份顺时针旋转 90∘90^\circ,其余两份保持原方向。随后按左上、左下、右下、右上的次序,用三条长度为 11 的线段连接相邻两份曲线的相接端点。各份曲线的外接正方形之间留出正好一格的间隔。

原 PDF 给出了 H1,H2,H3H_1,H_2,H_3 的图示,并标注了 H3H_3 的中空方格。

输入格式

输入一行一个整数 nn。

输出格式

输出一行一个非负整数,表示被水填满的方格数取模后的结果。

样例

3
26

H3H_3 有 2828 个中空方格。从上往下数第三行最左、最右的两个中空方格不会被水填满,所以答案为 2626。

4
100
12
2137408

数据范围

对于全部数据,1≤n≤101071\le n\le10^{10^7}。

原题子任务 nn 上限 分值
1 1212 20
2 10001000
3 10710^7
4 101810^{18}
5 1010710^{10^7}

原 PDF 题面与图示