P3394 Robot's Domain [暂无数据]

可前往 [P5102](https://www.luogu.com.cn/problem/P5102) 提交。

A robot starts from the origin $O$ of the $xOy$ plane and runs according to a given program. In the program, a letter $\texttt{E/S/W/N}$ means the robot moves $1$ meter to the east / south / west / north, respectively. We are given a program with $N$ instructions. The robot will continuously execute this program $\bm K$ times. Starting from the origin, after completing each step, the robot places a mark at the lattice point where it stands (it also leaves one at the origin). After all executions finish, how many $1 \times 1$ small squares have all four vertices marked at least once?

The first line contains two integers $N, K$. The second line contains a string of length $N$ (containing only characters $\texttt{E/S/W/N}$) representing the given program.

Output a single integer, the answer.

Constraints | Subtask ID | $N \le$ | $K \le$ | Score | |:-:|:-:|:-:|:-:| | 1 | 50 | 1 | 20 | | 2 | $10^5$ | 1 | 20 | | 3 | 50 | $10^9$ | 20 | | 4 | $10^5$ | $10^9$ | 40 | For $100\%$ of the testdata, $1 \le N \le 10^5$, $1 \le K \le 10^9$. Translated by ChatGPT 5