#P11483. [2023省队模拟]写题
[2023省队模拟]写题
题目描述
星鼻鼹鼠部落的横截面是一条 阶 CCF 曲线。把曲线的各条单位线段视为墙,在曲线范围内,从上方开口可以沿没有墙阻挡的相邻方格到达的方格称为中空方格。
最上面一行的所有中空方格都会被水填满。水可以穿过没有墙阻挡的格边,从已经填满的中空方格流向它的左边、右边或下边的中空方格。
求最终被水填满的方格数,对质数 取模。
CCF 曲线
记 阶 CCF 曲线为 。 由单位正方形的左边、下边、右边组成,上边留作开口。
由 构造 时,将 复制为四份,按 排列。左上角的一份逆时针旋转 ,右上角的一份顺时针旋转 ,其余两份保持原方向。随后按左上、左下、右下、右上的次序,用三条长度为 的线段连接相邻两份曲线的相接端点。各份曲线的外接正方形之间留出正好一格的间隔。
原 PDF 给出了 的图示,并标注了 的中空方格。
输入格式
输入一行一个整数 。
输出格式
输出一行一个非负整数,表示被水填满的方格数取模后的结果。
样例
3
26
有 个中空方格。从上往下数第三行最左、最右的两个中空方格不会被水填满,所以答案为 。
4
100
12
2137408
数据范围
对于全部数据,。
| 原题子任务 | 上限 | 分值 |
|---|---|---|
| 1 | 20 | |
| 2 | ||
| 3 | ||
| 4 | ||
| 5 |