本来在做图论...做POJ3613...结果怎么搞都搞不出...到网上搜了下解题报告...Floyd+矩阵乘法...矩阵乘法虽然线代早学了..但写程序没用过..就看了下Matrix67的http://www.matrix67.com/blog/archives/276里面说的很清楚了...然后我自己写的时候..为了乘法时不写错..可以这么想..类比Floyd判断更新时的...i,j,k分别代表行列和做和的顺序...三层1~N..
得到的矩阵点[ i ] [ j ]+=第一个矩阵[ i ] [ k ] * 第二个矩阵[ k ] [ j ] ...似想 line[ i -> j ] 由 k 点更新...思维就比较准确了..
矩阵加法很简单..a举证和b举证对应的点直接相加就是了...
Matrix64大牛文章关于矩阵乘法的性质已经说得很清楚了...将一列矩阵乘法提出公因式计算的效率比直接算高很多...所以在做矩阵乘法时主要一点就是要灵活的提取公因式..
回到这道题...首先 A^1+A^2+A^3+.......A^k 若k%2==0 可分解为 ( A^1+A^2+A^3...A^(k/2-1) ) + A^(k/2)*( A^1+A^2+A^2+....A^k ) 若是k%2==1..则最后一项多出来...
再一个求 A^k ..若 k 为偶数 A^k = A^(k/2) * A^(k/2) 若 k 为奇数A^k = A^(k/2) * A^(k/2)*A
而取模在先取模再做加法或者先取模再做乘法结果是一样的..所以可以根据这两个性质用两个递归来解决这个问题...为了方便数据传递..我使用结构体来存矩阵的..
Program:
分享到:
相关推荐
北大POJ2002-Squares 解题报告+AC代码
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ3020-Antenna Placement 解题报告+AC代码
这是魔兽世界终极版POJ的-测试数据,找了好久才找到的。 本来想设置为0积分,但是它居然自动收费(o_ _)ノ。 看传送门:https://pan.baidu.com/s/1cCIwW8psGDASu2JdZawG3Q
POJ3211--Washing Clothes
北大POJ3414-Pots 解题报告+AC代码
北大POJ2305-Basic remains POJ2305-Basic remains
北大POJ3273-Monthly Expense POJ3273-Monthly Expense
北大POJ1321-Chess Problem POJ1321-Chess Problem
北大POJ1080-Human Gene Functions POJ1080-Human Gene Functions
北大POJ1159-Palindrome 解题报告+AC代码
poj 1000-3000部分代码 网上收集
北大POJ1159-Palindrome
北大POJ1258-Agri-Net【Prim】 解题报告+AC代码
北大POJ1837-Balance
北大POJ2503-Babelfish 解题报告+AC代码
北大POJ1201-Intervals 解题报告+AC代码
北大POJ1011-Sticks 解题报告+AC代码