解题思路

核心思路：本题是稀疏 Mixture-of-Experts 上一次带容量约束的两阶段自适应路由。先按当前专家原型做完整软指派，再把每个专家的原型改写成第一阶段实际接收特征的加权平均，这对应 EM / soft $k$-means 的一次「分配—更新」；然后用新原型从匹配分数开始重新路由。第一阶段结果只用于更新原型，计分只用第二阶段匹配分数，进不了专家的激活走残差分支。

实现方法：

• 每个输入块按绝对值峰值做特征归一化：$A_{i,k}=X_{i,k}\times Q/M_i$，全零块置零。除法一律向零取整。
• 匹配分数 $S_{i,j}=\max(A_i\cdot P_j,0)$。$T_i>0$ 时先按比例拆 $f_{i,j}=L_i\times S_{i,j}/T_i$，余数只补给 $S_{i,j}>0$ 的专家，按分数降序、编号升序各加 $1$。
• 专家超容量时按 $g_{i,j}=f_{i,j}\times C_j/U_j$ 裁剪，再按原份额降序、输入块编号升序回填；之后按输入块编号把剩余激活补进「仍有空位且 $S_{i,j}>0$」中分数最高的专家，一次送 $\min(D,E)$。

题目描述

某稀疏 MoE 模型有 $n$ 个输入块、$m$ 个专家。每个输入块是 $d$ 维特征，并带若干可拆分的激活，激活可分给多个专家。每个专家有一个 $d$ 维路由原型，一次最多处理定额个激活。

先按初始原型完整路由一轮，再按本轮实际接收量改写原型，然后用新原型从头再路由一轮。第二轮结束后，用进入专家的激活和未进入专家的残差激活计算路由质量。

输入块、专家、特征维均按输入顺序从 $1$ 编号。

记特征归一化尺度为 $Q$，残差分支系数为 $R$。

下文中的所有除法均为整数除法，商向零取整。

1. 特征归一化

对于输入块 $i$，定义其特征绝对值峰值为

$$M_i=\max_{k=1}^{d}|X_{i,k}|.$$

如果 $M_i=0$，则该输入块归一化后的所有特征均为 $0$。

否则，第 $k$ 维归一化特征定义为

$$A_{i,k}=X_{i,k}\times Q/M_i.$$

2. 专家匹配

专家 $j$ 当前维护的路由原型为 $P_{j,1},P_{j,2},\ldots,P_{j,d}$。

输入块 $i$ 与专家 $j$ 的原始匹配分数为

$$S_{i,j}=\sum_{k=1}^{d}A_{i,k}\times P_{j,k}.$$

如果计算结果小于 $0$，则令

$$S_{i,j}=0.$$

只有满足 $S_{i,j}>0$ 的专家，才能处理输入块 $i$ 的激活。

3. 初始路由

输入块 $i$ 携带 $L_i$ 个激活单元。

定义该输入块与所有专家的总匹配强度为

$$T_i=\sum_{j=1}^{m}S_{i,j}.$$

如果 $T_i=0$，则本阶段不向任何专家发送激活。

否则，按匹配分数比例给专家 $j$ 分配

$$f_{i,j}=L_i\times S_{i,j}/T_i$$

个激活单元。

此时若还有

$$L_i-\sum_{j=1}^{m}f_{i,j}$$

个未分配激活，只考虑 $S_{i,j}>0$ 的专家：按 $S_{i,j}$ 从大到小，分数相同则编号小的优先，每个专家至多再得 $1$ 个。一轮补完仍有剩余的，本步不再分配。

4. 专家容量限制

专家 $j$ 在一次路由过程中最多能够处理 $C_j$ 个激活单元。

定义初始发送给专家 $j$ 的激活总量为

$$U_j=\sum_{i=1}^{n}f_{i,j}.$$

如果 $U_j\le C_j$，保持 $f_{i,j}$ 不变。

否则按容量裁剪。

首先，对于输入块 $i$，保留

$$g_{i,j}=f_{i,j}\times C_j/U_j$$

个激活单元。

随后，专家 $j$ 仍可继续接收的激活数量为

$$C_j-\sum_{i=1}^{n}g_{i,j}.$$

此时只考虑满足 $f_{i,j}>0$ 的输入块。

按照原始路由量 $f_{i,j}$ 从大到小排序。如果 $f_{i,j}$ 相同，则输入块编号较小者优先。

按照上述顺序依次处理，每个输入块至多额外恢复 $1$ 个激活单元。

一轮补完仍未到容量上限的，多余容量空着。

完成容量限制后，专家 $j$ 的剩余处理能力定义为

$$C_j-\text{专家当前实际接收的激活总量}.$$

5. 空闲专家重路由

容量限制后，按输入块编号从小到大处理尚未进入专家的激活。

设当前输入块 $i$ 已经发送给专家 $j$ 的激活数量为 $h_{i,j}$。

输入块 $i$ 当前尚未处理的激活数量为

$$L_i-\sum_{j=1}^{m}h_{i,j}.$$

当该值仍然大于 $0$ 时，在所有同时满足以下条件的专家中进行选择：

• 专家仍有剩余处理能力；
• $S_{i,j}>0$。

从中选择匹配分数 $S_{i,j}$ 最大的专家。

如果存在多个匹配分数相同的专家，则选择编号最小的专家。

设输入块当前剩余激活数量为 $D$，该专家当前剩余处理能力为 $E$，则一次向该专家发送

$$\min(D,E)$$

个激活。

随后同步减少输入块的剩余激活数量和专家的剩余处理能力。

重复直到该块没有剩余激活，或没有满足条件的专家。仍未路由的激活进入本阶段残差分支。

6. 专家原型更新

第一阶段路由结束后，各专家根据自己实际接收到的输入块更新路由原型。

对于专家 $j$，定义其第一阶段实际处理的激活总量为

$$W_j=\sum_{i=1}^{n}h_{i,j}.$$

如果 $W_j=0$，原型不变。

否则，专家 $j$ 更新后的第 $k$ 维路由原型为

$$P'_{j,k}=\frac{\sum_{i=1}^{n}h_{i,j}\times A_{i,k}}{W_j}.$$

7. 第二阶段路由

使用第 $6$ 步得到的新专家原型，从第 $2$ 步开始重新执行一次完整路由，即重新进行：

专家匹配、初始路由、专家容量限制和空闲专家重路由。

第二阶段仍然使用原始的专家容量 $C_j$ 和原始输入激活数量 $L_i$。

第一阶段的路由结果只用于专家原型更新，不会直接保留到第二阶段。

记第二阶段结束后，输入块 $i$ 最终发送给专家 $j$ 的激活数量为 $h'_{i,j}$。

记使用新专家原型计算得到的第二阶段匹配分数为 $S'_{i,j}$。

8. 路由质量

对于输入块 $i$，第二阶段结束后仍未进入任何专家的激活数量定义为

$$B_i=L_i-\sum_{j=1}^{m}h'_{i,j}.$$

定义输入块 $i$ 的正向特征能量为

$$G_i=\sum_{k=1}^{d}\max(A_{i,k},0).$$

输入块 $i$ 的路由质量为

$$\sum_{j=1}^{m}h'_{i,j}\times S'_{i,j}+B_i\times R\times G_i/100.$$

总路由质量为各输入块路由质量之和。

第二阶段中，专家 $j$ 的最终处理量为

$$\sum_{i=1}^{n}h'_{i,j}.$$

模型最终进入残差分支的激活总量为

$$\sum_{i=1}^{n}B_i.$$

输入描述

第一行包含五个整数 $n,m,d,Q,R$。

接下来 $n$ 行，每行包含 $d$ 个整数。

第 $i$ 行的 $d$ 个整数 $X_{i,1},X_{i,2},\ldots,X_{i,d}$ 表示输入块 $i$ 的原始特征。

接下来 $m$ 行，每行包含 $d$ 个整数。

第 $j$ 行的 $d$ 个整数 $P_{j,1},P_{j,2},\ldots,P_{j,d}$ 表示专家 $j$ 的初始路由原型。

接下来一行包含 $m$ 个整数 $C_1,C_2,\ldots,C_m$，其中 $C_j$ 表示专家 $j$ 在一次路由中最多能够处理的激活单元数量。

最后一行包含 $n$ 个整数 $L_1,L_2,\ldots,L_n$，其中 $L_i$ 表示输入块 $i$ 携带的激活单元数量。

数据范围

$1\le n\le400$

$1\le m\le40$

$1\le d\le12$

$1\le Q\le100$

$0\le R\le100$

$-500\le X_{i,k},P_{j,k}\le500$

$0\le C_j\le20000$

$1\le L_i\le80$

输出描述

第一行输出一个整数，表示模型第二阶段结束后的总路由质量。

第二行输出 $m$ 个整数，表示各专家在第二阶段最终实际处理的激活单元数量，按照专家编号从小到大输出，相邻整数之间以一个空格分隔。

第三行输出一个整数，表示最终进入残差分支的激活单元总数。

样例 1

输入

3 2 2 10 50
2 0
0 -4
3 3
1 0
0 -1
3 2
2 2 2

输出

540
3 2
1

样例说明

三个输入块归一化后的特征分别为 $(10,0)$、$(0,-10)$、$(10,10)$。

第一阶段中，三个输入块与两个专家的匹配分数分别为 $(10,0)$、$(0,10)$ 和 $(10,10)$。

完成初始路由后，三个输入块分别向两个专家发送 $(2,0)$、$(0,2)$ 和 $(1,1)$ 个激活。

专家 $2$ 收到 $3$ 个激活，但其最大处理能力为 $2$，因此需要进行容量限制。处理完成后，第一阶段最终路由结果为 $(2,0)$、$(0,2)$ 和 $(1,0)$。

此时两个专家均没有剩余处理能力，因此输入块 $3$ 剩余的 $1$ 个激活进入残差分支。

根据第一阶段实际进入专家的输入特征更新路由原型后，两个专家的新原型分别为 $(10,3)$ 和 $(0,-10)$。

第二阶段重新计算匹配分数，三个输入块与两个专家的匹配分数变为 $(100,0)$、$(0,100)$ 和 $(130,0)$。

经过第二阶段完整路由后，三个输入块最终分别向两个专家发送 $(2,0)$、$(0,2)$ 和 $(1,0)$ 个激活。

输入块 $3$ 仍有 $1$ 个激活进入残差分支。

三个输入块的正向特征能量分别为 $10$、$0$ 和 $20$。

因此总路由质量为

$$2\times100+2\times100+1\times130+1\times50\times20/100=540.$$

两个专家的最终处理量分别为 $3$ 和 $2$，残差分支处理的激活总量为 $1$。

样例 2

输入

3 2 2 6 100
4 0
0 4
1 1
1 0
0 1
1 5
2 2 2

输出

234
1 5
0

样例说明

归一化后，三个输入块的特征分别为 $(6,0)$、$(0,6)$ 和 $(6,6)$。

第一阶段初始路由结果分别为 $(2,0)$、$(0,2)$ 和 $(1,1)$。

专家 $1$ 的最大处理能力只有 $1$，容量限制后，三个输入块暂时分别得到 $(1,0)$、$(0,2)$ 和 $(0,1)$ 的路由结果。

此时专家 $2$ 仍有 $2$ 个空闲计算位置。

输入块 $1$ 与专家 $2$ 的匹配分数为 $0$，因此无法重路由到专家 $2$。

输入块 $3$ 剩余的 $1$ 个激活可以发送给专家 $2$。

第一阶段最终路由结果因此为 $(1,0)$、$(0,2)$ 和 $(0,2)$。

专家原型更新后，两个专家的新路由原型分别为 $(6,0)$ 和 $(3,6)$。

第二阶段中，三个输入块与两个专家的匹配分数分别为 $(36,18)$、$(0,36)$ 和 $(36,54)$。

完成第二阶段路由后，最终结果分别为 $(1,1)$、$(0,2)$ 和 $(0,2)$。

所有激活均成功进入专家，不存在残差激活。

因此总路由质量为

$$36+18+72+108=234.$$

两个专家的最终处理量分别为 $1$ 和 $5$，残差分支处理的激活总量为 $0$。