#P9180. Cube Rotate
Cube Rotate
Cube Rotate(滚动立方体)
题目描述
桌上有一个立方体,六个面各写着一个 1 到 1000 之间的整数,且互不相同。每次滚动时,立方体绕底面的一条边翻转,使原来的顶面转到前、后、左、右四个方向之一。
乘积初始为 1。每次滚动结束后,把此时前面的数字乘入乘积,并对 998244353 取模。初始前面的数字不单独乘入。
给出立方体的初始状态、最终状态、最终乘积,以及一部分滚动方向。请计算有多少种填法能补全所有遗忘的方向,同时满足这两项最终记录。两个填法只要在任意一次滚动的方向不同,就算不同方案。
输入格式
第一行一个整数 T(1 ≤ T ≤ 10),表示测试用例数。每组用例包含:
-
一行一个整数 n(1 ≤ n ≤ 200,000),表示滚动次数。
-
一行 n 个整数 a₁ 到 aₙ,每个整数的含义如下:
值 含义 0 这次的方向未知 1 原顶面转到前面 2 原顶面转到后面 3 原顶面转到左面 4 原顶面转到右面 -
接下来两行各有六个整数,分别表示初始状态和最终状态,顺序均为前、后、左、右、上、下。
-
最后一行一个整数 k,表示最终乘积对 998244353 取模后的记录。
设 m 为方向序列中 0 的个数,保证 1 ≤ m ≤ 20。一个输入文件中,同时满足 n ≥ 100,000 和 m ≥ 20 的用例不超过 5 组。
输出格式
每组用例输出一行一个整数,表示符合要求的方向序列总数。没有符合要求的序列时输出 0。方案数不取模,请使用 64 位整数。
样例
1
7
3 0 4 2 0 4 4
1 6 2 3 4 5
1 6 4 5 3 2
3
1
唯一可行的方向序列为 3 4 4 2 1 4 4。七次滚动后的前面数字依次是 1 1 1 3 1 1 1。
来源:2022 年中国大学生算法设计超级联赛第 5 场,1009 Cube Rotate。原题 PDF