Slot Strategy 2 (Hard)

题目描述

这个问题是问题 C 的更难版本，卷轴数量为 $N$ 而不是三个，并且 $M$ 的上限更大。

有一个有 $N$ 个卷轴的老虎机。
第 $i$ 个卷轴上符号的排列由字符串 $S_i$ 表示。这里，$S_i$ 是长度为 $M$ 的由数字组成的字符串。 每个卷轴都有一个相应的按钮。对于每个非负整数 $t$，Takahashi 可以在卷轴开始转动后恰好 $t$ 秒时选择按下一个按钮或什么也不做。
如果他在卷轴开始转动后恰好 $t$ 秒按下对应第 $i$ 个卷轴的按钮，第 $i$ 个卷轴将停止并显示 $S_i$ 的第 $((t \bmod M)+1)$ 个字符。
这里，$t \bmod M$ 表示 $t$ 除以 $M$ 的余数。 Takahashi 想要停止所有卷轴，使得所有显示的字符都相同。
求从开始转动到所有卷轴停止且达到他目标的最小可能秒数。
如果这是不可能的，请报告该事实。

输入格式

输入从标准输入给出，格式如下： $N$ $M$ $S_1$ $\vdots$ $S_N$

输出格式

如果不可能使所有卷轴停止后显示相同字符，输出 $-1$.
否则，输出从开始转动到达到该状态的最小可能秒数。

3 10
1937458062
8124690357
2385760149

6

10 20
01234567890123456789
01234567890123456789
01234567890123456789
01234567890123456789
01234567890123456789
01234567890123456789
01234567890123456789
01234567890123456789
01234567890123456789
01234567890123456789

90

5 10
0000000000
1111111111
2222222222
3333333333
4444444444

-1

10 20
14159265358979323846
26433832795028841971
69399375105820974944
59230781640628620899
86280348253421170679
82148086513282306647
09384460955058223172
53594081284811174502
84102701938521105559
64462294895493038196

11

提示

$1 \leq N \leq 100$ $1 \leq M \leq 10^5$ $N$ 和 $M$ 为整数。 $S_i$ 是长度为 $M$ 的由数字组成的字符串。Takahashi 可以如下停止每个卷轴，使得在卷轴开始转动后 $6$ 秒时，所有卷轴都显示 $8$。

在卷轴开始转动后 $0$ 秒按下对应第二个卷轴的按钮。第二个卷轴停止并显示 $8$，即 $S_2$ 的第 $((0 \bmod 10)+1=1)$ 个字符。 在卷轴开始转动后 $2$ 秒按下对应第三个卷轴的按钮。第三个卷轴停止并显示 $8$，即 $S_3$ 的第 $((2 \bmod 10)+1=3)$ 个字符。 在卷轴开始转动后 $6$ 秒按下对应第一个卷轴的按钮。第一个卷轴停止并显示 $8$，即 $S_1$ 的第 $((6 \bmod 10)+1=7)$ 个字符。

没有在 $5$ 秒或更少时间内使卷轴显示相同字符的方法，因此输出 $6$.
注意他必须停止所有卷轴并使它们显示相同的字符。
不可能使卷轴停止后所有显示的字符都相同。
在这种情况下，输出 $-1$.

标签: AtCoder|abc320G

来源

AtCoder|abc320G