传统题 1000ms 512MiB

【明月杯3H】残月

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

Constantine被武汉的天气整麻了,在迷糊之中有了一个idea.

题目描述

在一个 nnn * n的正方形点阵上,选取点构造两个正方形,要求如下:

  • 正方形的顶点与点阵的点重合
  • 正方形的边水平或竖直
  • 两个正方形有且仅有一个公共点,且公共点为两个正方形的顶点
  • 两个正方形没有相邻的边

请问对于一个 nnn * n 的点阵,有多少种符合上述条件的构造方案,由于答案可能很大,请对 998244353998244353 取模后输出.

为明确题意,有以下几个例子:

由于两个正方形存在相邻边,所以这种构造是非法的.

由于两个正方形存在相邻边,所以这种构造是非法的.

由于蓝色正方形的边不满足水平或者竖直,所以这种构造是非法

这个构造方式是合法的.

对于 n=3n = 3 的情况,我们有以下 22 种合法构造方案

输入格式

一行,一个整数 nn.

输出格式

一行,一个整数,代表合法方案数.

样例 #1

样例输入 #1

3

样例输出 #1

2

样例 #2

样例输入 #2

4

样例输出 #2

12

提示

对于 20%20\% 的数据,n1e3n\le 1e3

对于 60%60\% 的数据,n1e6n\le 1e6

对于 100%100\% 的数据,n1e9n\le 1e9

明月杯3

未参加
状态
已结束
规则
OI
题目
10
开始于
2024-4-10 18:30
结束于
2024-4-10 22:30
持续时间
4 小时
主持人
参赛人数
35