Hyperboxes
SRM 710 · 2017-02-20 · by lg5293
Problem Statement
You are given three
We are in an k-dimensional space that has an orthogonal coordinate system. We are interested in k-dimensional hyperboxes that have sides parallel to the axes of the coordinate system. Formally, each such hyperbox can be described by 2k coordinates: x_{1,1}, x_{1,2}, x_{2,1}, x_{2,2}, ..., x_{k,1}, x_{k,2}. This sequence of coordinates denotes the hyperbox that contains points with the following property: for each i, the i-th coordinate of the point is between x_{i,1} and x_{i,2}, inclusive.
Each hyperbox must have a positive hypervolume. That is, for each i, x_{i,1} must be strictly smaller than x_{i,2}. Additionally, in this problem we will restrict our attention to hyperboxes with the following property: each of the 2k coordinates of the hyperbox is an integer between 1 and n, inclusive.
Two hyperboxes intersect if they share at least one point, so touching at a corner still counts as intersecting. Two hyperboxes are disjoint if they do not intersect.
We want to select m mutually disjoint hyperboxes with the above properties, and we want to label them from 1 to m. Count and return the number of ways to do so, modulo 998244353.
(Note that the hyperboxes are labeled. Two ways of selecting them are different even if just the labels differ.)
Constraints
- n will be between 2 and 10^9.
- m will be between 1 and 6.
- k will be between 1 and 10^9.
5 1 1 Returns: 10
We want to choose a single 1-dimensional hyperbox, i.e., a line segment. The coordinates of its endpoints must be integers between 1 and 5, inclusive. The number of ways to select the hyperbox is (5 choose 2) = 10.
5 2 1 Returns: 10
Now we want to choose two disjoint 1-dimensional hypercubes. In other words, we want two disjoint line segments in the given range of coordinates. There are 10 ways of doing so. Remember that the hyperboxes are labeled. The choice where hyperbox 1 has coordinates (1,2) and hyperbox 2 has coordinates (3,5) differs from the choice where hyperbox 1 has coordinates (3,5) and hyperbox 2 has coordinates (1,2).
5 1 2 Returns: 100
Here we want a single 2-dimensional hyperbox - in other words, a rectangle.
4 2 2 Returns: 140
710 3 710 Returns: 980029536
Don't forget about the mod.
Submissions are judged against all 129 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Hyperboxes with a public method int findCount(int n, int m, int k) · 129 test cases · 2 s / 256 MB per case