tioj 1711 山洞

矩陣累乘


因為當下狀態只受最後兩排影響


且這兩排有69種組合


我就開了69*69的矩陣


我的排列矩陣中，只有第一排是有用的，其餘都是廢物


初始矩陣：i=1~69, j=1 ( 1 )，i=1~69, j=2~69 ( 0 )
-> 代表最後兩排第 1 種～第69種都有一種排法


遞移矩陣：要用程式跑，先跑完才開始做累乘
-> mat[i][j]=0 代表第 i 種會被第 j 種卡到


然後用快速冪logn求出答案


http://codepad.org/GTV5gZmu