#P18185. Again Permutation Problem
Again Permutation Problem
Again Permutation Problem
给定 个 的排列。第 个排列记为 。
最初,序列 。你可以执行任意次以下操作,也可以不执行:
- 选择一个 ,把 更新为 。
考虑经过任意次操作后所有能够得到的不同序列 。求这些序列的逆序数之和,对 取模。
序列的逆序数是满足 且 的下标对 的个数。同一序列无论可以用多少种操作序列得到,都只统计一次。
输入格式
第一行两个整数 。
接下来 行,每行 个整数,第 行表示排列 。
输出格式
输出一个整数,表示所有可达不同序列的逆序数之和,模 。
数据范围
- ;
- 每个 都是 的一个排列;
- 不同的 可以相同,也可以是恒等排列;
- 所有输入均为整数。
样例 1
输入
3 2
1 2 3
2 3 1
输出
4
样例 2
输入
5 2
3 4 5 1 2
1 5 4 3 2
输出
50
样例 3
输入
30 12
1 2 9 4 5 6 7 8 3 10 11 12 19 14 15 25 17 18 20 26 21 22 23 24 16 29 27 28 13 30
9 2 27 4 5 10 7 8 1 25 11 12 24 14 15 16 17 18 19 20 21 22 23 28 6 26 3 13 29 30
1 5 3 29 2 6 7 8 9 10 11 12 13 16 15 18 17 14 19 20 21 22 28 27 25 26 24 23 4 30
7 2 3 25 5 6 1 28 21 15 11 12 13 14 10 17 16 18 19 20 9 22 23 24 4 26 27 8 29 30
1 2 5 4 16 6 7 8 9 11 10 3 13 14 15 12 17 23 19 20 21 29 18 24 25 26 27 28 22 30
19 24 3 4 1 6 7 8 9 10 11 12 13 21 15 16 17 18 5 22 20 14 23 2 25 26 27 28 29 30
1 2 3 4 5 6 27 8 9 10 29 12 24 14 15 16 17 18 30 20 7 22 13 23 25 26 21 28 11 19
1 2 25 4 5 6 7 8 9 20 23 12 13 14 15 16 17 18 19 10 29 22 3 24 11 26 27 28 30 21
1 2 16 4 5 6 3 8 9 10 11 12 22 29 13 7 17 18 19 20 21 15 23 24 14 26 27 28 25 30
1 13 3 4 5 6 21 8 24 10 7 12 20 14 15 16 17 2 19 18 11 22 23 9 25 26 27 28 29 30
1 2 3 4 5 6 25 8 9 19 11 12 13 7 10 16 21 18 15 20 17 22 23 24 28 26 27 14 29 30
1 2 27 21 5 6 7 8 9 10 18 24 13 14 15 16 17 12 19 11 4 22 23 20 25 26 3 28 29 30
输出
701414999
样例 1 中恰有三个可达序列 、、,逆序数分别为 ,所以答案为 。