問題一覧 > 通常問題

No.3033 エルハートの数え上げ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 14
作問者 : ジュ・ビオレ・グレイス / テスター : 👑 p-adic
0 ProblemId : 11844 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-02-10 22:33:46

問題文

三次元座標空間内の閉半空間 Hm={(x,y,z)∈R3:Amx+Bmy+Cmz+Dm≥0}H_m = \{ (x,y,z) \in \mathbb{R}^3 : A_mx + B_my + C_mz + D_m \geq 0\} が 与えられます(m=1,…,M, (Am.Bm,Cm)≠(0,0,0)m = 1, \dots, M, \ (A_m. B_m, C_m) \neq (0, 0, 0))。
これらは P:=H1∩⋯∩HM\mathcal P := H_1 \cap \dots \cap H_M が [−15,15]3[-15, 15]^3 に含まれるような3次元の整凸多面体(頂点が格子点である凸多面体)となるように与えられます。
原点を中心とする P\mathcal P の NN 倍相似拡大 NP:={(Nx,Ny,Nz):(x,y,z)∈P}N\mathcal P := \{ (Nx, Ny, Nz) : (x,y,z) \in \mathcal P\} の内部にある格子点の個数を 998244353998244353 で割った余りを求めてください。

以下は用語と入力についての説明です。

  • 凸多面体 P\mathcal P が「3次元」であるとは、P\mathcal P がある平面上に乗っていることがない、すなわち体積が 0 ではないという意味です。
  • P\mathcal P の「内部」とは開半空間 Hm′={(x,y,z)∈R3:Amx+Bmy+Cmz+Dm>0}H'_m = \{ (x,y,z) \in \mathbb{R}^3 : A_mx + B_my + C_mz + D_m > 0\} たちの共通部分 H1′∩⋯∩HM′H'_1 \cap \dots \cap H'_M のことです。
  • 入力には「無駄な」ものがありません。つまり、H1,…,HMH_1, \dots, H_M のいずれか一つでも除くと、P\mathcal P とは異なる図形になってしまいます。
  • Am,Bm,Cm,DmA_m, B_m, C_m, D_m は互いに素です。
  • P\mathcal P とそれを囲む閉半空間 H1,…,HMH_1, \dots, H_M は、[−15,15]3[-15, 15]^3 に含まれるいくつかの格子点の凸包として計算されたものになっています。

入力

N MN \ M
A1 B1 C1 D1A_1 \ B_1 \ C_1 \ D_1
⋮\vdots
AM BM CM DMA_M \ B_M \ C_M \ D_M

1≤N≤109,1 \leq N \leq 10^9,
4≤M≤20,4 \leq M \leq 20,
−109≤Am,Bm,Cm,Dm≤109.-10^9 \leq A_m, B_m, C_m, D_m \leq 10^9.

出力

最後に改行してください。

サンプル

サンプル1
入力
10 6
0 -1 0 10
-1 0 0 10
0 1 0 0
0 0 -1 10
0 0 1 0
1 0 0 0
出力
970299

この入力から与えられる閉半空間たちの共通部分は、一辺の長さが 1010 の立方体である。これを 1010 倍相似拡大すると一辺 100100 の立方体になり、内部にある点の個数は 993=97029999^3 = 970299 個となる。

サンプル2
入力
123 8
-1 -1 1 1
-1 -1 -1 1
-1 1 1 1
1 1 -1 1
1 -1 -1 1
1 -1 1 1
1 1 1 1
-1 1 -1 1
出力
2451225

この入力から与えられる閉半空間たちの共通部分は、以下の八面体である:

NN 倍相似拡大の内部に含まれる点の個数を求めてみる。0≤k≤N−10 \leq k \leq N-1 として、z=N−kz = N-k を固定して切断した xyxy-平面を考えると、そこにある格子点は (±k,0),(0,±k)(\pm k, 0), (0, \pm k) を頂点に持つ正方形の内部にある格子点である。
簡単な計算からこの平面上には格子点が 2(k−1)k+12(k-1)k + 1 個あることが分かる。これを、k=1,…,N−1k = 1, \dots, N-1 について足し合わせると、zz-座標が正の格子点の個数が求まる。したがって、求めるものは

2∑k=1N−1[2(k−1)k+1]+(2(N−1)N+1)=23(N−1)N(2N−1)+2(N−1)+1.\displaystyle2 \sum_{k = 1}^{N-1} [2(k-1)k + 1] + (2(N-1)N + 1) = \frac{2}{3}(N-1)N(2N-1) + 2(N-1) + 1.

N=123N = 123 のときを計算すると 24512252451225 となる。

サンプル3
入力
134656493 14
0 5 -6 75
-15 -10 8 195
-15 5 -4 240
-75 -105 32 810
15 10 17 180
10 15 -14 145
30 45 14 435
-15 10 -7 270
0 -15 -7 150
195 -75 221 1725
65 -25 -42 575
-15 -21 8 162
-15 -30 4 225
-15 -30 14 225
出力
902145025

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。