#P9771. [2020年省队模拟]howto

    ID: 6395 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2700省选/NOI-不变量分析群奇偶性分析重复元素除重二分图建模普通并查集乘法原理

[2020年省队模拟]howto

题目描述

给定一个 nn 行 mm 列的整数矩阵 ss。一次操作可以选一行,将这一行的元素从左到右倒序排列,或者选一列,将这一列的元素从上到下倒序排列。可以执行任意次操作。

求从初始矩阵出发能得到多少种不同的矩阵。只要有一个位置上的值不同,就视为不同的矩阵。答案对 10910^9 取模。

输入格式

第一行一个整数 TT,表示数据组数。

对于每组数据,第一行两个整数 n,mn,m。接下来 nn 行,每行 mm 个整数,表示初始矩阵 ss。

输出格式

输出 TT 行,每行一个整数,表示对应答案对 10910^9 取模后的结果。

样例

5
1 6
1 1 4 5 1 4
1 6
1 1 4 4 1 1
4 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
4 4
1 2 2 1
3 4 4 3
5 6 6 5
7 8 8 7
5 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
2
1
165888
1296
663552

其余三个样例见原题下发文件中的 ex_howto2.in/out、ex_howto3.in/out、ex_howto4.in/out,分别满足原题测试点 6–7、13–14、15–20 的条件。

数据范围

对于全部数据,1≤T≤101\le T\le10,1≤n,m≤5001\le n,m\le500,1≤si,j≤nm1\le s_{i,j}\le nm。

原题测试点 nn mm 额外性质
1–2 =1=1 ≤500\le500 无
3–5 =2=2 所有数互不相同
6–7 ≤500\le500
8–9 ≤5\le5 无
10–12 =2=2 ≤500\le500 每一行都是回文
13–14 ≤500\le500
15–20 无

原题题面图片