No.3033 エルハートの数え上げ
タグ : / 解いたユーザー数 14
作問者 :
ジュ・ビオレ・グレイス
/ テスター :
👑 
p-adic
問題文
三次元座標空間内の閉半空間 $H_m = \{ (x,y,z) \in \mathbb{R}^3 : A_mx + B_my + C_mz + D_m \geq 0\}$ が 与えられます($m = 1, \dots, M, \ (A_m. B_m, C_m) \neq (0, 0, 0)$)。
これらは $\mathcal P := H_1 \cap \dots \cap H_M$ が $[-15, 15]^3$ に含まれるような3次元の整凸多面体(頂点が格子点である凸多面体)となるように与えられます。
原点を中心とする $\mathcal P$ の $N$ 倍相似拡大 $N\mathcal P := \{ (Nx, Ny, Nz) : (x,y,z) \in \mathcal P\}$ の内部にある格子点の個数を $998244353$ で割った余りを求めてください。
以下は用語と入力についての説明です。
- 凸多面体 $\mathcal P$ が「3次元」であるとは、$\mathcal P$ がある平面上に乗っていることがない、すなわち体積が 0 ではないという意味です。
- $\mathcal P$ の「内部」とは開半空間 $H'_m = \{ (x,y,z) \in \mathbb{R}^3 : A_mx + B_my + C_mz + D_m > 0\}$ たちの共通部分 $H'_1 \cap \dots \cap H'_M$ のことです。
- 入力には「無駄な」ものがありません。つまり、$H_1, \dots, H_M$ のいずれか一つでも除くと、$\mathcal P$ とは異なる図形になってしまいます。
- $A_m, B_m, C_m, D_m$ は互いに素です。
- $\mathcal P$ とそれを囲む閉半空間 $H_1, \dots, H_M$ は、$[-15, 15]^3$ に含まれるいくつかの格子点の凸包として計算されたものになっています。
入力
$N \ M$ $A_1 \ B_1 \ C_1 \ D_1$ $\vdots$ $A_M \ B_M \ C_M \ D_M$
$1 \leq N \leq 10^9,$
$4 \leq M \leq 20,$
$-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
この入力から与えられる閉半空間たちの共通部分は、一辺の長さが $10$ の立方体である。これを $10$ 倍相似拡大すると一辺 $100$ の立方体になり、内部にある点の個数は $99^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
この入力から与えられる閉半空間たちの共通部分は、以下の八面体である:
$N$ 倍相似拡大の内部に含まれる点の個数を求めてみる。$0 \leq k \leq N-1$ として、$z = N-k$ を固定して切断した $xy$-平面を考えると、そこにある格子点は $(\pm k, 0), (0, \pm k)$ を頂点に持つ正方形の内部にある格子点である。
簡単な計算からこの平面上には格子点が $2(k-1)k + 1$ 個あることが分かる。これを、$k = 1, \dots, N-1$ について足し合わせると、$z$-座標が正の格子点の個数が求まる。したがって、求めるものは
$\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 = 123$ のときを計算すると $2451225$ となる。
サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。