Skip to content

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了,可以的话,请您参考添加页面,与大家一起分享你的题解!