2155. A Repeating Roll Pattern, a Billion Billion Rolls

A token starts on square 1 of a track of n squares, with jumps that work exactly as in #2148: at most one per roll, never chaining, and a roll whose target is past square n is wasted and moves nothing.

The rolls are not a list this time. A pattern of L rolls is given, and it repeats for ever: roll 1 is the first entry, roll L the last, roll L + 1 the first again. Exactly k rolls are made.

Print the final square and the number of wasted rolls.

The catch is k, which reaches 10^18. Carrying out 10^18 rolls at a billion a second takes about thirty years.

``` n = 10, no jumps, pattern 2 3, k = 4 -> 8 1

1 -> 3 -> 6 -> 8, then 8 + 3 = 11 is past the end, so that roll is wasted ```

``` n = 10, no jumps, pattern 2 3, k = 10^18 -> 10 999999999999999996

after the trace above, the fifth roll is 2 and takes the token 8 -> 10, and from square 10 both 2 and 3 overshoot, so every roll from the sixth onwards is wasted. Exactly four rolls ever move the token. ```

## What most people try first

A loop over k. Correct and unfinishable. The next idea is usually to run one whole pattern and multiply, which is wrong because the token is on a different square at the start of each pass, so each pass does something different.

## The state is a PAIR, and there are not many of them

What determines the future is not the square alone and not the position in the pattern alone, but both together:

state = (square, index into the pattern)

There are at most n * L such states, which is at most 100000 at the stated limits. Each state has exactly one successor, so after at most n * L + 1 rolls a state must repeat, and from that point the whole sequence of rolls repeats identically for ever. The sequence of states is a tail followed by a loop:

roll: 0 1 2 ... s-1 | s s+1 ... s+c-1 | s s+1 ... [----- the tail ----] [-- the loop, length c --] [ again ...

Record, for every state met, the roll number it was first met at AND the number of rolls wasted up to that point. When a state recurs at roll t having first appeared at roll s:

loop length c = t - s wasted per loop = wastedAt(t) - wastedAt(s)

Then skip whole loops in one step: with rem = k - t rolls still to make, do rem / c whole loops by adding rem / c times the per-loop waste to the total, and advance the roll counter by rem / c times c. What is left is fewer than c rolls, which are carried out one at a time, and the token's square is already correct because skipping whole loops returns it to the state it was in.

## Why the skip is exact

Let step be the function taking one state to the next. The loop found means step applied c times to the state at roll s gives that same state. Since step is a function, applying it c more times gives the same state again, so by induction the state at roll s + i + jc equals the state at roll s + i for every i and every j at least 0.

The waste is where care is needed, because unlike the square it ACCUMULATES rather than repeating. The rolls from s to t - 1 form one complete loop, and the rolls from s + jc to s + (j+1)c - 1 pass through exactly the same states in the same order, so each of them wastes exactly the same amount. The per-loop waste is therefore constant and multiplying it by the number of whole loops is exact. That is the one place where a problem of this shape differs from #2147, where the answer depended only on the state reached and nothing had to be accumulated.

## Overflow

k reaches 10^18, and so does the answer for the wasted count, since every roll may be wasted. The signed 32 bit limit is 2147483647, so both need 64 bits; signed 64 bit reaches about 9.2 * 10^18, so 10^18 and the products formed from it are inside it, because the per-loop waste is at most c and (rem / c) * c is at most k.

JavaScript needs BigInt for k and for the wasted total: a plain Number is exact only below 2^53, about 9.007 * 10^15, so 10^18 is not the value in the input and the division rem / c on it would be wrong. Square numbers and pattern indices stay small and need no BigInt.

## Cost

O(n L) states visited at most once each, so O(n L) time and memory, independent of k. At the limits that is 100000 states whether k is 4 or 10^18.

Constraints - `1 ≤ n ≤ 1000` - `0 ≤ m ≤ n` - `1 ≤ L ≤ 100` - `1 ≤ k ≤ 10^18` - `1 ≤ a, b ≤ n` and `a` is never equal to `b` - no square is the start of two different jumps - `1 ≤ each roll ≤ 6` - a jump is taken at most once per roll and never chains - `k` and the wasted count both exceed `2^53`, so JavaScript needs BigInt for them