#P4967. 黑暗打击

    ID: 4892 远端评测题 100ms 250MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2018O2优化矩阵加速,矩阵优化线性递推,递推式构造

黑暗打击

题目背景

注,此题和 CQOI 的鼹鼠不一样,请仔细看题!本题只是借用背景!

在茫茫宇宙中……

题目描述

有一群生物ccj,他们在上次的星系中,发现了一群低等生物,于是想进行一波黑暗森林打击。这群低等生物即是 Hilbert\mathsf{Hilbert} 鼹鼠,生活在 Hilbert\mathsf{Hilbert} 星球,住在 Hilbert\mathsf{Hilbert} 曲线土壤内。
这群生物决定用最傻的办法——灌水,来淹死他们。现在“高等”生物想知道,对于 nn 阶的 Hilbert\mathsf{Hilbert} 曲线,从上往下灌水,能淹没几个单位面积?

这是 11~44 阶的 Hilbert\mathsf{Hilbert} 曲线:

fuck

h1h_1,如最左图所示,是一个缺上口的正方形,这个正方形的边长为 11。 从h2h_2 开始,按照以下方法构造曲线 hih_i: 将 hi1h_{i-1} 复制四份,按 2×22\times2 摆放。
把左上一份逆时针转 9090^{\circ },右上一份顺时针转 9090^{\circ },然后用三条单位线段将四分曲线按照左上-左下-右下-右上的顺序连接起来。如图所示,分别展示的是 h2h_2h3h_3h4h_4。加粗的线段是额外用于连接的线段。

灌水方式:

(显然这个是 h3h_3 的灌水面积)绿色即为无法被灌到的地方,红色为可以灌到的地方,灰色为墙,所以答案是 2626,即为样例1。

fuck

一个方格有水当且仅当在它的上,左,右方格中有至少一个方格有水,最上面一层的空格都有水。

注,此题要求对 92233720368547757839223372036854775783 取模

输入格式

一个整数 nn,表示这个洞穴是 nn 阶的 Hilbert\mathsf{Hilbert} 曲线。

输出格式

一个整数 ansans,表示有 ansans 个单位面积被淹没。

3

26

4

100

12
2137408

提示

样例解释:

自己数一数嘛……

n<=1010000n<=10^{10000}

详细范围参见“标程”

数据均为手动构造,请注意常数!