题目内容

在端侧设备部署神经网络模型时，通常需要对权重进行结构化剪枝，以降低参数量和计算开销。本题要求对权重矩阵按行进行基于 $L1$ 范数的剪枝，并利用剪枝后的矩阵完成分类预测。

设输入矩阵为 $X$，维度为 $n \times d$，其中 $n$ 表示样本数，$d$ 表示输入特征数。权重矩阵为 $W$，维度为 $d \times c$，其中 $c$ 表示输出类别数。

未剪枝时的前向计算流程如下：

• 线性变换：$h = XW$，结果维度为 $n \times c$。
• Softmax 激活：$y = \operatorname{softmax}(h)$，对每一行独立计算概率分布。第 $i$ 行第 $j$ 列的值为

• 预测标签：第 $i$ 个样本的预测标签为 $label_i = \arg\max_j y_{ij}$。由于 softmax 在每一行上保持相对顺序不变，因此该标签等价于 $label_i = \arg\max_j h_{ij}$。

剪枝的目标是删除权重矩阵 $W$ 中不重要的整行，也就是移除对应的输入特征。剪枝比例由 $ratio$ 给出，重要性使用每一行权重的 $L1$ 范数衡量。对于第 $i$ 行，其 $L1$ 范数定义为

剪枝流程如下：

首先，对 $W$ 的每一行计算 $L1$ 范数。

其次，计算需要删除的行数 $k = \lfloor ratio \times d \rfloor$。若 $ratio > 0$ 且 $k = 0$，则令 $k = 1$，保证至少删除 1 行。

然后，选择 $L1$ 范数最小的 $k$ 行删除，得到剪枝后的权重矩阵 $W'$，维度为 $(d-k) \times c$。

接着，从输入矩阵 $X$ 中删除相同的 $k$ 个特征列，得到 $X'$，维度为 $n \times (d-k)$。

最后，使用剪枝后的矩阵计算线性变换 $h' = X' W'$，再按上述 softmax 和 argmax 规则得到每个样本的预测标签。

约束条件：

输入维度 $n,d,c$ 均为 1 到 64 之间的整数；剪枝比例 $ratio$ 为 0 到 1.0 之间的浮点数。

输入描述

第一行包含三个整数 $n$、$d$、$c$，分别表示样本数、输入特征数和输出类别数。

接下来 $n$ 行，每行包含 $d$ 个浮点数，构成输入矩阵 $X$。

再接下来 $d$ 行，每行包含 $c$ 个浮点数，构成权重矩阵 $W$。

最后一行包含一个浮点数 $ratio$，表示剪枝比例。

输出描述

输出一行，包含 $n$ 个整数，用空格分隔。第 $i$ 个整数表示第 $i$ 个样本的预测类别下标。

样例1

输入

3 4 3
1 0 0 0
0 1 0 0
0 0 1 0
1 2 3
0 0 1
2 0 1
1 1 0
0.25

输出

2 0 0

说明

剪枝比例 $r=0.25$，需要删除行数 $k=\lfloor 0.25 \times 4 \rfloor=1$。

权重每一行的 $L_1$ 范数分别为：第 0 行 $|1|+|2|+|3|=6$，第 1 行 $|0|+|0|+|1|=1$，第 2 行 $|2|+|0|+|1|=3$，第 3 行 $|1|+|1|+|0|=2$。最小的是第 1 行，因此删除输入特征 1。

保留特征 0、2、3 后，第 1 个样本的剪枝后输入为 [1,0,0]，计算得到 $h'=[1,2,3]$，最大类别下标为 2。

第 2 个样本删除第 1 个特征后，保留特征取值均为 0，因此 $h'=[0,0,0]$，所有类别相同，取第一个类别 0。

第 3 个样本剪枝后保留特征 2 的值为 1，计算得到 $h'=[2,0,1]$，最大类别下标为 0。

样例2

输入

2 2 2
1 0
0 1
1 -1
-2 3
0

输出

0 1

说明

剪枝比例 $r=0$，因此删除行数 $k=\lfloor 0 \times 2 \rfloor=0$，不删除任何整行。

使用原权重矩阵计算线性变换。第 1 个样本的结果为 $h=[1,-1]$，最大类别下标为 0。

第 2 个样本的结果为 $h=[-2,3]$，最大类别下标为 1。

样例3

输入

2 3 2
1 0 0
0 0 1
1 0
2 0
0 3
0.1

输出

0 1

说明

剪枝比例 $r=0.1$，$d=3$，初始删除行数 $k=\lfloor 0.1 \times 3 \rfloor=0$。由于 $r>0$ 且 $k=0$，令 $k=1$，因此至少删除 1 行。

权重每一行的 $L_1$ 范数分别为：第 0 行 $|1|+|0|=1$，第 1 行 $|2|+|0|=2$，第 2 行 $|0|+|3|=3$。最小的是第 0 行，因此删除输入特征 0。

保留特征 1、2 后，第 1 个样本删除第 0 个特征后保留值均为 0，因此线性变换结果两个分量均为 0，最大类别下标为 0。

第 2 个样本删除第 0 个特征后，保留特征 2 的值为 1，计算得到 $h'=[0,3]$，最大类别下标为 1。