1287. Counting Distinct States With One Packed Key

A search state is a grid cell plus a set of collected keys: a row r and a column c, each from 0 to 49, and a keyring k from 0 to 63 used as six boolean flags. Given n states, print how many are DISTINCT.

(0,0,0) (0,0,0) (1,2,3) (0,0,1) -> 3

## What most people try first

A set of triples, or a three-dimensional array of booleans. Both work. The reason to pack instead is that a single integer key is what lets a visited set be one flat array, or one hash set of integers, with no tuple allocation and no nested indexing. In a search over states, which is where this shape comes from, the visited test runs once per edge and the allocation shows up.

## Mixed radix, not pure bit fields

The interesting part is that the row and column are NOT powers of two in size. They run 0 to 49, which is 50 values, and 50 is not a power of two. Two choices follow.

Pad each to 6 bits, since 2^6 = 64 >= 50, and the key becomes (r << 12) | (c << 6) | k, using 18 bits of which some combinations are unused.

Or pack the cell in MIXED RADIX as r * 50 + c, which uses exactly the 2500 values the grid has, and then shift that by the keyring's 6 bits:

key = ((r * 50 + c) << 6) | k

Both are correct. The second is denser, which matters when the key indexes a flat array: 2500 * 64 = 160000 entries against 2^18 = 262144. The reference uses it because the density argument is the one worth learning, and because mixing a radix with a shift is exactly what real state encodings do.

## Why the packing is injective, which is the only thing that matters

Two states give the same key only if they are the same state. The keyring occupies bits 0 to 5 and k < 64, so it never reaches bit 6, and the cell index occupies everything above. So equal keys force equal keyrings and equal cell indices. And r * 50 + c with c < 50 determines r and c uniquely, by division and remainder; that is the defining property of a radix.

Injectivity is the whole requirement. Any injective map into the integers works; density and speed are the only reasons to prefer one.

## Width

The largest key is (49 * 50 + 49) * 64 + 63 = 159999, which needs 18 bits. It fits in a signed 32-bit integer, whose limit is 2147483647, with thirteen bits to spare, so a flat array of 160000 entries is the natural visited set.

JavaScript is safe with plain Numbers, because every value involved is below 2^18 and << only truncates above bit 31. Nothing here needs 64 bits or BigInt. Had the grid been 1000 by 1000 with 20 keys, the key would have reached 10^6 * 2^20, past 32 bits, and this would have become #1281's problem.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ r ≤ 49` and `0 ≤ c ≤ 49` - `0 ≤ k ≤ 63`