P3010 [USACO11JAN] Dividing the Gold S

Bessie 和 Canmuu 找到了一袋 $N (1 \leq N \leq 250)$ 枚金币，他们希望尽可能均匀地分配这些金币。第 $i$ 枚金币的价值为 $v_i (1 \leq v_i \leq 2,000)$。奶牛们希望尽可能均匀地分割这堆金币，但这并不总是可能的。两个堆之间的最小价值差是多少？ 此外，Bessie 和 Canmuu 发现可能有多种方法以该最小差异分割金币。他们还想知道以最公平方式分割金币的方法数。如果无法均匀分割，Bessie 将得到价值较高的一堆。 例如，考虑一袋五枚金币，价值分别为：$2、1、8、4$ 和 $16$。Bessie 和 Canmuu 将金币分成两堆，一堆有一枚价值为 16 的金币，另一堆有剩下的金币，价值为 $1+2+4+8=15$。因此，差异为 $16-15 = 1$。这是他们以这种方式分割金币的唯一方法，所以均匀分割的方法数只有 $1$。 注意，相同价值的金币可以在堆之间交换，以增加执行最佳分割的方法数。因此，硬币集合 $\{1, 1, 1, 1\}$ 有六种不同的方法分割成两个最佳分区，每个分区有两枚硬币。

第 1 行：一个整数：$N$。 第 2 行到第 $N+1$ 行：第 $i+1$ 行包含一个整数：$V_i$。

第 1 行：一个整数，表示两个分区的最小差异。 第 2 行：一个整数，表示以第 1 行打印的最小差异分割金币的方法数。由于这个数可能会非常大，输出时请对 $1,000,000$ 取余。

（由 ChatGPT 4o 翻译）