#P1883. [Ipsc2007]Delicious Cake

    ID: 905 传统题 1000ms 512MiB 尝试: 17 已通过: 2 难度: 9 上传者: 标签>CF2700省选/NOI-轮廓线 DP轮廓状态规范化普通并查集预计算转移滚动数组高精度加法

[Ipsc2007]Delicious Cake

题目描述

Lenka 烤了一块长方形蛋糕。把蛋糕看成由 N×MN\times M 个单位方格组成的网格,只允许沿方格边界切割。没有被切开的公共边会把两个相邻方格连在一起,最终蛋糕分成若干个四连通的块。

如果两种切法得到的所有块在原蛋糕上的形状和位置都相同,则视为同一种切法。换句话说,同一个连通块内部不需要保留切痕。

求不同切法的数量。完全不切也算一种切法。

两行两列蛋糕的十二种切法

未分开任何连通块的切痕

输入格式

第一行一个正整数 TT,表示数据组数。接下来每组包含两个正整数 N,MN,M,分别表示蛋糕的两个边长。原赛输入在每组数据之前有一个空行。

输出格式

每组输出一行一个正整数,表示不同切法的精确数量。

样例

2

1 2

2 2
2
12

数据范围

附带解题报告给出的两边上限分别为 55 和 149149。旋转蛋糕不改变切法数量,输入的两边可以交换,因此可写为 1≤min⁡(N,M)≤51\le\min(N,M)\le5,1≤max⁡(N,M)≤1491\le\max(N,M)\le149。

IPSC 2007 原题 · 主办方题解