#P8687. [2018山东省队集训第一轮]弦形袋⿏

    ID: 8777 传统题 3000ms 256MiB 尝试: 2 已通过: 1 难度: 5 上传者: 标签>线性代数与代数高斯消元图论动态规划贪心CF1800数学矩阵树形DP

[2018山东省队集训第一轮]弦形袋⿏

弦形袋鼠 (kangaroo)

题目描述

法珞在教小朋友们简单的弦形袋鼠。

我们知道n×1n\times 1 的向量aa 和1×m1\times m的向量bb做乘法会得到n×mn\times m 的矩阵 Ai,j=aibjA_{i,j}=a_{i}b_{j} 。 现在给出一个矩阵BB,求一个最小的kk使得BB可以被表示为∑i=1kaibi\sum_{i=1}^{k} a_{i} b_{i} ,其中aia_{i} 是你任意指定的n×1n\times 1 的实数向量,bib_{i} 是你任意指定的1×m1\times m的实数向量。

输入格式

第一行两个正整数 n,mn,m。

接下来 nn 行,每行 mm 个整数 Bi,jB_{i,j},表示矩阵 BB。

输出格式

输出一行一个非负整数,表示最小的 kk。

数据范围

对于 100100% 的数据,n,m≤200,∣Bi,j∣≤106n,m\le 200,|B_{i,j}|\le 10^{6} 。