当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器：

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

1759：Matrix Revolution

题目描述
Lele 现在不仅会整数A+B，A*B，还会矩阵A+B，矩阵A*B。

一天，Lele在百无聊赖的时候，突然想起一个很无聊的问题。
对于给定的一个矩阵A，A+A^2+A^3+...+A^K 是多少呢？
其中A^2 表示两个矩阵的乘积A*A，A^3表示三个矩阵的乘积A*A*A，依此类推。

由于这个计算结果太大了，Lele无法把整个结果写出来，但是，他还是想请你告诉他，结果矩阵中到底有多少个非零元素。
输入解释
本题目包含多组测试，请处理到文件结束。
在每个测试数据的第一行，有三个整数N,M,和K(0<N<1000,0<=M<10*N,N<K<10^100)，其中N代表矩阵A的大小是N*N，K是题目中所描述的K。
接下来有M行，每行有三个整数a,b,c(0<=a,b,<N 且a!=b,0<c<10^9)表示矩阵中第a行第b列的值为c。(矩阵的行数和列数都是从0开始计数)

你可以假定矩阵中主对角线上的数都是1，其余没有提到的元素都是0。
输出解释
对于每一组测试数据，请在一行里输出结果矩阵里的非0元素的个数。
输入样例 
3 4 4
1 2 1
2 1 1
0 1 1
0 2 1
输出样例 
7
提示
Huge input,the C function scanf() will work better than cin
来自杭电HDUOJ的附加信息
Author linle
Recommend lcy
该题目是Virtual Judge题目，来自 杭电HDUOJ
题目来源 2007省赛集训队练习赛（6）_linle专场
源链接： HDU-1759
最后修改于 2020-10-25T22:47:43+00:00 由爬虫自动更新
共提交 0 次
通过率 --%
时间上限 内存上限
9000/3000MS(Java/Others) 32768/32768K(Java/Others)