← 返回题目列表

Codeforces · 1043/D

D. 神秘犯罪

中文机器翻译题面 查看原题

Acingel 是一个小镇。这里只有一位医生——艾达小姐。她很友善,从来没有人说过她的坏话,所以谁能想到艾达会被发现死在她的家里呢?世界著名侦探高里先生受命寻找罪犯。他向艾达的$$$m$$$邻居询问了在那不幸的一天拜访过她的客户的情况。我们将客户编号从 $$$1$$$ 到 $$$n$$$。每个邻居的证词都是这些数字的排列,描述了被询问的邻居见到客户的顺序。

然而,有些事实非常可疑——根据一些给定的排列,为什么有些客户是在早上见到的,而另一些客户却是在晚上见到的? “早上,一些邻居一定已经在睡觉了!” ——高里想——“晚上太黑了,看不清人的脸……”。现在他想在每个排列中删除一些前缀和一些后缀(前缀和后缀都可以为空),这样之后它们就非空并且彼此相等——一些潜在的犯罪分子可能会消失,但证词不会相互矛盾。

他可以通过多少种方式做到这一点?如果剩余的公共部分不同,则两种方式被称为不同。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 100\,000$$$, $$$1 \le m \le 10$$$)——嫌疑人的数量和被询问的邻居的数量。

接下来的 $$$m$$$ 行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$)。保证这些整数形成正确的排列(即,从 $$$1$$$ 到 $$$n$$$ 的每个数字恰好出现一次)。

输出

输出一个整数,表示删除每个排列的某些前缀和某些后缀的方法数(可能为空),使得剩余部分相等且非空。

示例

输入 #1

3 2
1 2 3
2 3 1

输出 #1

4

输入 #2

5 6
1 2 3 4 5
2 3 1 4 5
3 4 5 1 2
3 5 4 2 1
2 3 5 4 1
1 2 3 4 5

输出 #2

5

输入 #3

2 2
1 2
2 1

输出 #3

2

注意

在第一个示例中,所有可能的公共部分是 $$$[1]$$$、$$$[2]$$$、$$$[3]$$$ 和 $$$[2, 3]$$$。

在第二个和第三个示例中,只能保留长度为 $$$1$$$ 的公共部分。