3228. 千反田和折木奉太郎

单点时限: 10.0 sec

内存限制: 256 MB

千反田和折木奉太郎升入大学了。千反田同学为了更好的支持家族事业,努力学习理科知识。一日,他们在上完数学课后,发现了一道有趣的课后习题。

所有长度为 $n$ 的 01 序列,如果可以任意交换位置得到另外一个,我们认为是一类的,问本质不同有多少类?

这当然难不倒我们的千反田大小姐,长度为 $n$ 的 01 序列,如果包含 $k$ 个 1,那么凡是包含 $k$ 个 1 的序列本质都是相同的(因为可以任意交换嘛), 所以答案是 $n+1$。

这时候,折木同学就说:我们可以拓展这类问题,想想 $2 \times n$ 的 01 矩阵,可以任意交换两列,这个时候结果呢?

千反田瞪大了眼睛,说道:我很好奇!

折木同学开始解释了:我们可以同 Burnside 引理,考虑长度为 3 的 01 序列,一共有 8 种可能,交换方式一共 $3! = 6$ 种:

  • 对于 (1, 2, 3) 不动点个数是 8 个;
  • 对于 (1, 3, 2) 不动点个数是 4 个;
  • 对于 (2, 1, 3) 不动点个数是 4 个;
  • 对于 (2, 3, 1) 不动点个数是 2 个;
  • 对于 (3, 1, 2) 不动点个数是 2 个;
  • 对于 (3, 2, 1) 不动点个数是 4 个;

那么 $(8 + 4 + 4 + 2 + 2 + 4) \div 6 = 24 \div 6 = 4$。 是不是很奇妙?

好了那么给你个练习,给定 $n \times m$ 的 01 矩阵,可以交换任意两行两列,可以交换达到的矩阵认为是同一类,那么本质不同的有多少类呢?

千反田同学虽然学习了 Burnside,但是还是感觉迷迷糊糊的,你能否帮助她呢?

输入格式

$T$ 个 case。

每个 case 有 $n$, $m$ 两个整数 $1 \leq n, m \leq 10, n \cdot m \leq 25$。

输出格式

一行一个。对应的答案。

样例

Input
3
1 3
1 10
2 2
Output
4
11
7

9 人解决,28 人已尝试。

10 份提交通过,共有 42 份提交。

7.6 EMB 奖励。

创建: 3 年,4 月前.

修改: 3 年,1 月前.

最后提交: 3 年,4 月前.

来源: 2017 华东理工上海高校邀请赛

题目标签