P14836 [THUPC 2026 初赛] 能量分配

来自 2026 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2026）初赛。 题解等资源可在 查看。

小 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

从标准输入读入数据。 第一行输入一个正整数 $m(1\leq m\leq 12)$，表示学生总数。 接下来的 $m$ 行输入 $m\times m$ 的矩阵 $A$，其中每行 $m$ 个正整数，第 $i$ 行第 $j$ 列表示 $A_{i,j}$ 的取值，其中当 $i=j$ 时 $A_{i,j}=0$，当 $i\not=j$ 时有 $1

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

#### 样例一解释 对于 $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$ 所对应的分配方案的权值： | $280$ | $420$ | $504$ | | :---: | :---: | :---: | | $420$ | $420$ | $160$ | | $504$ | $160$ | $288$ | 各方案的权值和为 $3156$，对 $317$ 取模的结果为 $303$。