#P9180. Cube Rotate

    ID: 5262 传统题 20000ms 512MiB 尝试: 3 已通过: 1 难度: 4 上传者: 标签>动态规划CF1500模拟数学2022杭电多校

Cube Rotate

Cube Rotate(滚动立方体)

题目描述

桌上有一个立方体,六个面各写着一个 1 到 1000 之间的整数,且互不相同。每次滚动时,立方体绕底面的一条边翻转,使原来的顶面转到前、后、左、右四个方向之一。

乘积初始为 1。每次滚动结束后,把此时前面的数字乘入乘积,并对 998244353 取模。初始前面的数字不单独乘入。

给出立方体的初始状态、最终状态、最终乘积,以及一部分滚动方向。请计算有多少种填法能补全所有遗忘的方向,同时满足这两项最终记录。两个填法只要在任意一次滚动的方向不同,就算不同方案。

输入格式

第一行一个整数 T(1 ≤ T ≤ 10),表示测试用例数。每组用例包含:

  1. 一行一个整数 n(1 ≤ n ≤ 200,000),表示滚动次数。

  2. 一行 n 个整数 a₁ 到 aₙ,每个整数的含义如下:

    值 含义
    0 这次的方向未知
    1 原顶面转到前面
    2 原顶面转到后面
    3 原顶面转到左面
    4 原顶面转到右面
  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