AT_abc219_f [ABC219F] Cleaning Robot

题目描述

[ABC219F] 清扫机器人

问题描述

一个清扫机器人被放置在无限扩展的二维网格的方格 $(0, 0)$ 上。

给定了一个由四种类型的字符 L、R、U、D 组成的字符串程序。
机器人根据给定的程序，依次读取每个字符，并针对每个字符采取以下行动：

1. 将机器人的当前位置设为方格 $(x, y)$
2. 根据读取的字符执行以下移动：
   • 当读取 L 时：向左移动到方格 $(x-1, y)$。
   • 当读取 R 时：向右移动到方格 $(x+1, y)$。
   • 当读取 U 时：向上移动到方格 $(x, y-1)$。
   • 当读取 D 时：向下移动到方格 $(x, y+1)$。

给定一个由 L、R、U、D 组成的字符串 $S$ 和整数 $K$。机器人执行的程序是将字符串 $S$ 重复连接 $K$ 次。

一旦机器人访问过的方格（包括机器人的初始位置 $(0, 0)$）就会被清扫。
请输出在机器人执行程序结束后，被清扫的方格的数量。

输入格式

输入通过标准输入给出。

$S$ $K$

输出格式

输出在机器人执行程序结束后，被清扫的方格的数量。

样例 #1

样例输入 #1

RDRUL
2

样例输出 #1

7

样例 #2

样例输入 #2

LR
1000000000000

样例输出 #2

2

样例 #3

样例输入 #3

 UUURRDDDRRRUUUURDLLUURRRDDDDDDLLLLLLU
31415926535

样例输出 #3

219911485785

约束

• $S$是长度介于$1$和$2 \times 10^5$之间（包括$1$和$2 \times 10^5$）的字符串，由“l”、“R”、“u”和“d”组成。

• $1 \leq K \leq 10^{12}$

示例输出1

机器人将执行程序“rdrulrdrul”。它将从$(0, 0)$开始，按如下方式运行：

$(0, 0) \rightarrow (1, 0) \rightarrow (1, 1) \rightarrow (2, 1) \rightarrow (2, 0) \rightarrow (1, 0) \rightarrow (2, 0) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 0) \rightarrow (2, 0)$.

最后，七个方块将被清理：$(0, 0), (1, 0), (1, 1), (2, 0), (2, 1), (3, 0), (3, 1)$。

​

输入输出样例 #1

输入 #1

RDRUL
2

输出 #1

7

输入输出样例 #2

输入 #2

LR
1000000000000

输出 #2

2

输入输出样例 #3

输入 #3

UUURRDDDRRRUUUURDLLUURRRDDDDDDLLLLLLU
31415926535

输出 #3

219911485785