CF1210E.Wojtek and Card Tricks

Wojtek 刚刚在 Byteland 赢得了一场数学竞赛！奖品非常棒——一本名为《人人都能玩的纸牌戏法》的书。“太好了！”他想，“我终于可以用上那副一直闲置在桌子上的旧扑克牌了！”

书的第一章是“如何将 $k$ 张牌以任意顺序洗牌”。这实际上是 $n$ 种复杂洗牌方法的列表，每种方法都能以确定性的方式对 $k$ 张牌进行洗牌。具体来说，第 $i$ 种方法可以用一个排列 $ (P_{i,1}, P_{i,2}, \dots, P_{i,k}) $ 来描述，这个排列是 $1$ 到 $k$ 的整数的一个排列。如果我们将牌从上到下编号为 $1$ 到 $k$，那么 $P_{i,j}$ 表示洗牌后第 $j$ 张牌来自原来牌堆中的第 $P_{i,j}$ 张。

时间有限，Wojtek 今天只想学习其中的一部分戏法。他会选择两个整数 $l, r$（$1 \le l \le r \le n$），然后记住从第 $l$ 个到第 $r$ 个（包括两端）的所有戏法。接着，他会拿出一副已经排好序的 $k$ 张牌，不断随机应用他记住的戏法，直到他觉得无聊为止。他依然喜欢数学，所以他开始思考：在他停止洗牌后，他最多能得到多少种不同的牌堆？

Wojtek 还没有选定 $l$ 和 $r$，但他已经很好奇了。因此，他定义 $f(l, r)$ 表示如果他记住了第 $l$ 到第 $r$ 个戏法（包括两端），他最多能得到多少种不同的牌堆。请你计算：

$$\sum_{l=1}^n \sum_{r=l}^n f(l, r)$$

的值。

第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 200\,000$，$1 \le k \le 5$），分别表示戏法的数量和牌堆中的牌数。

接下来的 $n$ 行，每行描述一种戏法，由 $k$ 个互不相同的整数 $P_{i,1}, P_{i,2}, \dots, P_{i,k}$ 组成（$1 \le P_{i,j} \le k$）。

输出题目中所描述的总和的值。

考虑第一个样例：

• 第一个戏法交换了最上面的两张牌。
• 第二个戏法把最下面的一张牌放到牌堆顶。
• 第三个戏法交换了最下面的两张牌。

第一个或第三个戏法都只能让 Wojtek 得到两种不同的牌堆（即两张牌交换或不交换）。因此，$f(1,1) = f(3,3) = 2$。

第二个戏法可以让他以循环的方式洗牌，因此 $f(2,2) = 3$。

事实证明，前两个戏法或后两个戏法都足以让他以任意方式洗牌。因此，$f(1,2) = f(2,3) = f(1,3) = 3! = 6$。

由 ChatGPT 4.1 翻译