#P8687. [2018山东省队集训第一轮]弦形袋⿏
[2018山东省队集训第一轮]弦形袋⿏
弦形袋鼠 (kangaroo)
题目描述
法珞在教小朋友们简单的弦形袋鼠。
我们知道 的向量 和的向量做乘法会得到 的矩阵 。 现在给出一个矩阵,求一个最小的使得可以被表示为 ,其中 是你任意指定的 的实数向量, 是你任意指定的的实数向量。
输入格式
第一行两个正整数 。
接下来 行,每行 个整数 ,表示矩阵 。
输出格式
输出一行一个非负整数,表示最小的 。
数据范围
对于 % 的数据, 。
法珞在教小朋友们简单的弦形袋鼠。
我们知道n×1 的向量a 和1×m的向量b做乘法会得到n×m 的矩阵 Ai,j=aibj 。 现在给出一个矩阵B,求一个最小的k使得B可以被表示为∑i=1kaibi ,其中ai 是你任意指定的n×1 的实数向量,bi 是你任意指定的1×m的实数向量。
第一行两个正整数 n,m。
接下来 n 行,每行 m 个整数 Bi,j,表示矩阵 B。
输出一行一个非负整数,表示最小的 k。
对于 100% 的数据,n,m≤200,∣Bi,j∣≤106 。