Codeforces Round 963 (Div. 2) |
---|
Закончено |
Это сложная версия задачи. Единственное отличие заключается в том, что в этой версии $$$k \le 10^{12}$$$. Вы можете делать взломы только в том случае, если обе версии задачи решены.
Дан прямоугольник размером $$$w \times h$$$ на плоскости $$$Oxy$$$, с точками $$$(0, 0)$$$ в нижнем левом углу и $$$(w, h)$$$ в верхнем правом углу прямоугольника.
У вас также есть робот, изначально находящийся в точке $$$(0, 0)$$$, и сценарий $$$s$$$ из $$$n$$$ символов. Каждый символ является L, R, U или D, что указывает роботу двигаться влево, вправо, вверх или вниз соответственно.
Робот может двигаться только внутри прямоугольника; в противном случае он изменит сценарий $$$s$$$ следующим образом:
Затем он продолжит двигаться, следуя измененному сценарию, начиная с того символа, который не смог выполнить.
Сценарий $$$s$$$ будет выполняться $$$k$$$ раз подряд. Все изменения в строке $$$s$$$ будут сохраняться даже при повторении. В процессе выполнения, сколько раз робот переместится в точку $$$(0, 0)$$$? Обратите внимание, что начальная позиция не учитывается.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит четыре целых числа $$$n$$$, $$$k$$$, $$$w$$$ и $$$h$$$ ($$$1 \le n, w, h \le 10^6$$$; $$$1 \le k \le 10^{12}$$$).
Вторая строка содержит строку $$$s$$$ размера $$$n$$$ ($$$s_i \in \{\texttt{L}, \texttt{R}, \texttt{U}, \texttt{D}\}$$$) — сценарий, который необходимо выполнить.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^6$$$.
Для каждого набора входных данных выведите одно целое число — количество раз, когда робот переместится в $$$(0, 0)$$$ при выполнении сценария $$$s$$$ $$$k$$$ раз подряд.
62 4 2 2UR4 2 1 1LLDD6 3 3 1RLRRRL5 6 3 3RUURD7 5 3 4RRDLUUU7 123456789999 3 2ULULURD
1 4 3 1 1 41152263332
В первом наборе входных данных робот движется только вверх и вправо при первых двух исполнениях сценария. После этого он занимает позицию $$$(2, 2)$$$. При следующих двух исполнениях он двигается вниз и влево и заканчивает в $$$(0, 0)$$$. Поэтому ответ равен $$$1$$$.
Во втором наборе входных данных каждый раз при выполнении сценария робот посещает начало координат дважды. И поскольку $$$k=2$$$, он посещает начало координат $$$2 \cdot 2 = 4$$$ раза в общей сложности.
В третьем наборе входных данных визуализация показана ниже:
Название |
---|