题目内容

你需要实现一个基于计数特征的二分类预测算法。给定训练样本集与测试样本集，训练集的每条样本由 $m$ 个非负整数特征值和一个类别标签（$0$ 或 $1$）组成；测试集的每条样本仅包含 $m$ 个特征值。请严格按照以下步骤计算每个测试样本的预测类别：

1. 令 $N_c$ 为训练集中类别 $c$ 的样本数（$c \in \{0,1\}$），总样本数 $N = N_0 + N_1$。先验对数为：

   $$\ln \pi_c = \ln \frac{N_c}{N}$$

2. 对每个类别 $c$ 和每个特征维度 $j\;(1 \le j \le m)$，记 $n_{c,j}$ 为类别 $c$ 中所有样本在第 $j$ 个特征上的取值之和。使用加一平滑估计特征条件概率：

   $$P(j \mid c) = \frac{n_{c,j} + 1}{\sum_{k=1}^{m} (n_{c,k} + 1)}$$

   并计算其对数 $\ln P(j \mid c)$。

3. 对于一个测试样本 $\mathbf{x} = (x_1,\dots,x_m)$，定义其属于类别 $c$ 的对数得分：

   $$S_c = \ln \pi_c + \sum_{j=1}^{m} x_j \cdot \ln P(j \mid c)$$

4. 比较两类的得分：若 $S_1 \ge S_0$，则预测该样本为 $1$，否则预测为 $0$。

注意：为保证运行环境一致，请在程序开始时固定随机种子（例如 numpy.random.seed(42)）。

约束条件：

• 训练集样本数 $N$ 不超过 $10^4$，特征维度 $m$ 不超过 $500$。
• 所有特征值均为非负整数，单个样本的特征值总和不超过 $10^6$。类别标签为 $0$ 或 $1$。
• 训练集中两个类别均至少包含一个样本（即 $N_0>0$ 且 $N_1>0$）。
• 测试集样本数 $K$ 不超过 $10^4$，特征维度与训练集一致。

输入描述

输入为单个 JSON 对象，可能跨越多行。该对象包含两个字段：

• "train"：一个二维列表，形状为 $N imes (m+1)$。每一行由 $m$ 个非负整数特征值与一个类别标签（0 或 1）组成，标签位于行末。
• "test"：一个二维列表，形状为 $K imes m$。每一行包含 $m$ 个非负整数特征值。

特征维度 $m$ 对所有行保持一致，且满足上述约束。

输出描述

输出一个 JSON 数组，按顺序包含 $K$ 个整数，依次表示每个测试样本的预测类别（0 或 1）。

样例1

输入

{"train":[[2,0,0],[1,1,0],[0,2,1],[0,1,1]],"test":[[1,0],[0,1],[0,0]]}

输出

[0,1,1]

说明

训练集有 4 条样本，特征维度 $m=2$。类别计数：$N_0=2$，$N_1=2$，$N=4$；先验对数均为 $\ln\pi_0=\ln\pi_1=\ln 0.5\approx -0.6931$。

类别 $0$ 内特征求和：$n_{0,1}=2+1=3$，$n_{0,2}=0+1=1$，平滑分母 $\sum_{k}(n_{0,k}+1)=3+1+2=6$。条件概率对数：$\ln P(1|0)=\ln\frac{3+1}{6}=\ln\frac{4}{6}\approx -0.4055$，$\ln P(2|0)=\ln\frac{1+1}{6}=\ln\frac{2}{6}\approx -1.0986$。

类别 $1$ 内特征求和：$n_{1,1}=0+0=0$，$n_{1,2}=2+1=3$，平滑分母 $0+3+2=5$。条件对数：$\ln P(1|1)=\ln\frac{0+1}{5}=\ln 0.2\approx -1.6094$，$\ln P(2|1)=\ln\frac{3+1}{5}=\ln 0.8\approx -0.2231$。

测试样本 [1,0]：$S_0=-0.6931+1 imes(-0.4055)=-1.0986$，$S_1=-0.6931+1 imes(-1.6094)=-2.3025$，$S_0>S_1$，预测 0。样本 [0,1]：$S_0=-0.6931+1 imes(-1.0986)=-1.7918$，$S_1=-0.6931+1 imes(-0.2231)=-0.9163$，$S_1>S_0$，预测 1。样本 [0,0]：$S_0=S_1=-0.6931$，满足 $S_1\ge S_0$，预测 1。

样例2

输入

{"train":[[0,0],[2,1],[3,1]],"test":[[0],[10],[5]]}

输出

[1,1,1]

说明

训练集 $N=3$，$N_0=1$，$N_1=2$。先验对数 $\ln\pi_0=\ln(1/3)\approx -1.0986$，$\ln\pi_1=\ln(2/3)\approx -0.4055$。

特征维度 $m=1$。类别 $0$ 特征总和 $n_{0,1}=0$，平滑分母 $0+1=1$，$\ln P(1|0)=\ln 1=0$。类别 $1$ 特征总和 $n_{1,1}=2+3=5$，平滑分母 $5+1=6$，$\ln P(1|1)=\ln(6/6)=\ln 1=0$。

因此对于任意测试样本，条件概率得分为 $0$，最终得分仅由先验决定：$S_0=-1.0986$，$S_1=-0.4055$。由于 $S_1>S_0$，所有测试样本均预测 1。

样例3

输入

{"train":[[1,0,2,0],[0,3,1,0],[2,2,0,1],[0,1,3,1],[1,0,1,1]],"test":[[1,1,1],[2,0,0],[0,2,1]]}

输出

[1,1,0]

说明

训练集特征维度 $m=3$，样本数 $N=5$（$N_0=2$，$N_1=3$）。先验对数 $\ln\pi_0=\ln 0.4\approx -0.9163$，$\ln\pi_1=\ln 0.6\approx -0.5108$。

类别 $0$ 内特征求和：$n_{0,1}=1+0=1$，$n_{0,2}=0+3=3$，$n_{0,3}=2+1=3$。平滑分母 $\sum(n_{0,k}+1)=1+3+3+3=10$。条件对数：$\ln P(1|0)=\ln(2/10)\approx -1.6094$，$\ln P(2|0)=\ln(4/10)\approx -0.9163$，$\ln P(3|0)=\ln(4/10)\approx -0.9163$。

类别 $1$ 内特征求和：$n_{1,1}=2+0+1=3$，$n_{1,2}=2+1+0=3$，$n_{1,3}=0+3+1=4$。平滑分母 $3+3+4+3=13$。条件对数：$\ln P(1|1)=\ln(4/13)\approx -1.1787$，$\ln P(2|1)=\ln(4/13)\approx -1.1787$，$\ln P(3|1)=\ln(5/13)\approx -0.9555$。

测试样本 [1,1,1]：$S_0=-0.9163+ (-1.6094-0.9163-0.9163)=-4.3583$，$S_1=-0.5108+(-1.1787-1.1787-0.9555)=-3.8237$，$S_1>S_0$，预测 1。样本 [2,0,0]：$S_0=-0.9163+2 imes(-1.6094)=-4.1351$，$S_1=-0.5108+2 imes(-1.1787)=-2.8682$，$S_1>S_0$，预测 1。样本 [0,2,1]：$S_0=-0.9163+2 imes(-0.9163)+1 imes(-0.9163)=-3.6652$，$S_1=-0.5108+2 imes(-1.1787)+1 imes(-0.9555)=-3.8237$，此时 $S_0>S_1$，预测 0。