AdditionalFile7002.zip

#7002. 「THUPC 2026 初赛」能量分配

标签: 传统 | 时间限制: 4000 ms | 内存限制: 1024 MiB |

题目描述

小 Q 是星际小学光速飞船课的老师，她准备向学校的星际能源商店购买 $n$ 个本质不同的能量石，其中每个能量石具有一单位能量，且每个能量石有一个 $1$ 到 $n$ 之间的正整数编号，每个能量石的编号互不相同。她想要把它们分给 $m$ 名学生，帮助学生们练习如何驾驶光速飞船。

在分配时，每个能量石会恰好被分给一名学生，且允许学生没有分配到任何能量石。定义 $c_{i}$ 表示第 $i$ 名学生分配到的能量石总数，即满足 $\sum_{i=1}^{m} c_{i}=n$ 且 $c_{i} \geq 0$。两个能量石的分配方案本质不同当且仅当存在一个学生在两个方案中分配到的能量石的编号集合不同。例如对于两个能量石与两名学生，能量石 $1$ 分给学生 $1$，能量石 $2$ 分给学生 $2$ 与能量石 1 分给学生 $2$，能量石 $2$ 分给学生 $1$ 被视为两种本质不同的方案，由于学生 $1$ 在方案一中分配到的能量石的编号集合为 $\{1\}$ 而在方案二中分配到的能量石的编号集合为 $\{2\}$ ，所以被视为本质不同的方案。

然而，每名学生都想要自己分配到的用于光速飞船的能量石比其他学生分到的多，因此如果一个学生分配到的能量石比其他学生分到的能量石要更多，那么他会将拥有更大的满意度。

初始时每名学生的满意度为 $1$，则在分配完 $n$ 个能量石后第 $i$ 名学生的满意度可以按照如下方式计算：

• 依次考虑每一个除了 $i$ 自己以外的学生 $j$，若 $c_{i}>c_{j}$，则 $i$ 的满意度将会变为原来的 $A_{i, j}$ 倍；若 $c_{i}=c_{j}$，则 $i$ 的满意度将会变为原来的 $B_{i, j}$ 倍；若 $c_{i}<c_{j}$，则 $i$的满意度将不会发生变化。保证满足 $1<B_{i, j}<A_{i, j} \leq 10^{9}$。

对于第 $i$ 名学生，令其在分配完 $n$ 个能量石后的满意度为按照如上方式考虑完除自己以外的 $m-1$ 名学生后最终的满意度。现在小 Q 定义一个能量石的分配方案的权值为在分完 $n$ 个能量石后 $m$ 名学生满意度之积，小 Q 想知道所有本质不同的能量分配方案的权值和对 $317$ 取模的结果。然而小 Q 是光速飞船课老师，不是光速计算课老师，所以她希望精通光速计算的您，迅速告诉她这个结果对 $317$ 取模的结果。

此外，由于小 Q 事先没有测试星际小学光速飞船的具体性能，当光速飞船的性能不同时，能量需求会发生变化。所以她会询问 $q$ 个可能购买的能量石总数 $n$，对于每一个 $n$，您需要告诉她所有若她购买了 $n$ 个能量石，所有能量石的分配方案的权值和对 $317$ 取模的结果。

输入格式

从标准输入读入数据。

第一行输入一个正整数 $m$ $\left(1 \leq m \leq 12\right)$，表示学生总数。

接下来的 $m$ 行输入 $m \times m$ 的矩阵 $A$，其中每行 $m$ 个正整数，第 $i$ 行第 $j$ 列表示 $A_{i, j}$ 的取值，其中当 $i=j$ 时 $A_{i, j}=0$，当 $i \neq j$ 时有 $1<A_{i, j} \leq 10^{9}$。

接下来的 $m$ 行输入 $m \times m$ 的矩阵 $B$ ，其中每行 $m$ 个正整数，第 $i$ 行第 $j$ 列表示 $B_{i, j}$ 的取值，其中当 $i=j$ 时 $B_{i, j}=0$，当 $i \neq j$ 时有 $1<B_{i, j}<A_{i, j}$。

之后一行输入一个正整数 $q$ $\left(1 \leq q \leq 100\right)$ ，表示 $q$ 个询问。

接下来的 $q$ 行每行一个正整数 $n$ $\left(1 \leq n \leq 10^{18}\right)$，表示询问当能量石总数为 $n$ 时原问题的答案。

输出格式

输出到标准输出。

输出 $q$ 行，每行一个 $[0,317)$ 之间的整数，表示能量石的分配方案权值和对 $317$ 取模的结果。

样例 1

输入

3
0 7 5
5 0 7
4 6 0
0 4 4
3 0 4
3 2 0
4
1
2
10
1000000000000000000

输出

37
303
46
148

对于 $n=1$，共有 $3$ 种本质不同的能量石的分配方案，即将唯一的能量石分配给学生 $1,2$ 或 $3$，每种方案的权值分别为 $280,420,288$ ，所有分配方案的权值和为 $988$，对 $317$ 取模的结果为 $37$。

对于 $n=2$，共有 $9$ 种本质不同的能量石的分配方案，对于每一组满足 $1 \leq i, j \leq 3$的正整数对 $(i, j)$ ，能量石 $1$ 分配给学生 $i$ ，能量石 $2$ 分配给学生 $j$ 对应一组方案，各方案的权值如下表，其中第 $i$ 行第 $j$ 列的数表示将能量石 $1$ 分配给学生 $i$ ，能量石 $2$ 分配给学生 $j$ 所对应的分配方案的权值：

$$\begin{array}{|l|l|l|} \hline 280 & 420 & 504 \\ \hline 420 & 420 & 160 \\ \hline 504 & 160 & 288 \\ \hline \end{array}$$

各方案的权值和为 $3156$，对 $317$ 取模的结果为 $303$。

题目使用协议

来自 THUPC2026（2026年清华大学学生程序设计竞赛暨高校邀请赛）初赛。

以下『本仓库』皆指 THUPC2026 初赛 官方仓库（https://gitlink.org.cn/thusaa/thupc2026pre）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；
2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；
3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库地址 或 算协公开仓库链接。