#P3581. 扑克牌

    ID: 2782 传统题 5000ms 512MiB 尝试: 28 已通过: 10 难度: 9 上传者: 标签>CF2800省选/NOI-双射计数回溯搜索对称性去重状压 DP计数 DP欧拉路径记忆化搜索滚动数组哈希表By

扑克牌

题目描述

我们有 nn 张纸牌,每张牌都有数字和颜色两个属性。今天我心情不错,想把这 nn 张牌排成一行,使得相邻的两个要么颜色相同要么数字相同。数字在 00 到 99 之间,颜色有红黄蓝三种(用 0,1,20,1,2 来表示)。想让你求出方案数。

输入格式

第一行输入 nn,表示有 nn 张纸牌。接下来 nn 行,每行两个数字分别表示第 ii 张牌的颜色和数字。

输出格式

一行输出答案,对 2322^{32} 取模。

3
0 0
0 0
0 0
6
3
0 1
0 2
1 2
2

数据规模与约定

对于 100%100\% 的数据满足 n≤30n\le 30,最多只会有 33 种颜色,且不会有 44 张牌的数字和颜色都一样。

题目来源

By 佚名提供