#P17489. PM14952 子多边形面积和

PM14952 子多边形面积和

题目描述

设 PP 是一个严格凸多边形,VV 是它的顶点集合。对于任意满足 ∣W∣≥3|W|\ge 3 的顶点子集 W⊆VW\subseteq V,WW 的凸包称为 PP 的一个子多边形。

现在给定一个特殊的凸多边形 PP。它有 4n4n 个顶点,且所有顶点坐标均为整数。你需要求出 PP 的所有子多边形的面积之和。

多边形 PP 按如下方式构造:

  1. 考虑顶点为 (n,0)(n,0)、(0,n)(0,n)、(−n,0)(-n,0)、(0,−n)(0,-n) 的正方形(旋转了 45∘45^\circ)。其边界上恰好有 4n4n 个整点。
  2. 从其中任意一个整点开始,沿逆时针方向依次将这些整点记为 T0,T1,…,T4n−1T_0,T_1,\ldots,T_{4n-1}。
  3. 任取平面上的一个点作为 P0P_0。
  4. 对 1≤i≤4n1\le i\le 4n,令 Pi=Pi−1+Ti−1P_i=P_{i-1}+T_{i-1},其中点的加法按坐标分别相加。
  5. 最终的多边形 PP 的顶点为 P0,P1,…,P4n−1P_0,P_1,\ldots,P_{4n-1}。

可以证明,无论构造过程中选择哪个起点以及哪个 P0P_0,最终要求的答案都相同。

设所有子多边形面积之和写成最简分数 A/BA/B,其中 gcd⁡(A,B)=1\gcd(A,B)=1。设 B−1B^{-1} 表示 BB 在模 998244353998244353 意义下的乘法逆元,请输出

A⋅B−1 mod 998244353A\cdot B^{-1}\bmod 998244353。

输入格式

输入一行一个整数 nn。

输出格式

输出一个整数,表示答案对 998244353998244353 取模后的结果。

数据范围

1≤n≤1250001\le n\le 125000。