11268: 【原1268】矩阵迭代

题目

题目描述

author: BogoSort 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1268

Description

Zzy大神在用迭代法求矩阵特征值的时候发现，迭代矩阵 \( M \) 的幂随指数增加会变得很大。Zzy还发现，对于不同的矩阵 \( M \) ，它们增长的速度是不同的，有些被限制在多项式级别，有些则会指数增长。现在Zzy想知道一些特殊的矩阵，0/1方阵，迭代时增长的速度。

对于矩阵 \( M=(m_{ij}) \) ，定义 \( sum(M)=\sigma(m_{ij}) \) 。

对于给定的n阶0/1方阵，请你判断函数 \( f(l)=sum(M^l) \) 是否是多项式级别，如果是，请求出最小的 \( k \)，使得 \( f(l)=O(l^k) \) 。

Input Format

输入共有n+1行。

第1行有1个整数n，表示矩阵的阶数。

其余n行，每行n个整数（0或1），给出指定的0/1方阵。

对于所有数据，n不超过50。

Output Format

输出一个整数m，若 \( f(l) \) 是多项式级别则输出最小的 \( k \)，否则输出-1。

Sample Input

3
0 1 1
1 0 1
0 1 1

Sample Output

-1

Sample Input

5
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
0 0 0 0 0

Sample Output

0

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！