No.3033 Ehrhart Counting
タグ : / 解いたユーザー数 13
作問者 :
ジュ・ビオレ・グレイス
/ テスター :
👑 
p-adic
Problem Statement
You are given closed half-spaces $H_m = \{ (x,y,z) \in \mathbb{R}^3 : A_mx + B_my + C_mz + D_m \geq 0\}$ in three-dimensional coordinate space ($m = 1, \dots, M, \ (A_m. B_m, C_m) \neq (0, 0, 0)$).
They are given so that $\mathcal P := H_1 \cap \dots \cap H_M$ is a three-dimensional integral convex polytope (a convex polytope whose vertices are lattice points) contained in $[-15, 15]^3$.
Find the number of lattice points in the interior of $N\mathcal P := \{ (Nx, Ny, Nz) : (x,y,z) \in \mathcal P\}$, the homothetic expansion of $\mathcal P$ by a factor of $N$ centered at the origin, modulo $998244353$.
The terms and the input are explained below.
- A convex polytope $\mathcal P$ being "three-dimensional" means that $\mathcal P$ does not lie on any plane, that is, its volume is not 0.
- The "interior" of $\mathcal P$ is the intersection $H'_1 \cap \dots \cap H'_M$ of the open half-spaces $H'_m = \{ (x,y,z) \in \mathbb{R}^3 : A_mx + B_my + C_mz + D_m > 0\}$.
- The input contains no "redundant" half-spaces. That is, removing any one of $H_1, \dots, H_M$ results in a shape different from $\mathcal P$.
- $A_m, B_m, C_m, D_m$ are coprime.
- $\mathcal P$ and the closed half-spaces $H_1, \dots, H_M$ enclosing it have been computed as the convex hull of some lattice points contained in $[-15, 15]^3$.
Input
$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.$
Output
Print a newline at the end.
Sample
Sample 1
Input
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
Output
970299
The intersection of the closed half-spaces given by this input is a cube with side length $10$. Expanding it by a factor of $10$ gives a cube with side length $100$, and the number of points in its interior is $99^3 = 970299$.
Sample 2
Input
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
Output
2451225
The intersection of the closed half-spaces given by this input is the following octahedron:
Let us count the points contained in the interior of the expansion by a factor of $N$. For $0 \leq k \leq N-1$, consider the $xy$-plane cut by fixing $z = N-k$. The lattice points on it are the lattice points in the interior of the square with vertices $(\pm k, 0), (0, \pm k)$.
A simple calculation shows that this plane contains $2(k-1)k + 1$ lattice points. Summing this over $k = 1, \dots, N-1$ gives the number of lattice points with positive $z$-coordinate. Therefore, the desired count is
$\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.$
For $N = 123$, this evaluates to $2451225$.
Sample 3
Input
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
Output
902145025
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。