【題意】：有n只貓咪，開(kāi)始時(shí)每只貓咪有花生0顆，現(xiàn)有一組操作，由下面三個(gè)中的k個(gè)操作組成：
               1. g i 給i只貓咪一顆花生米
               2. e i 讓第i只貓咪吃掉它擁有的所有花生米
               3. s i j 將貓咪i與貓咪j的擁有的花生米交換

               現(xiàn)將上述一組操作做m次后，問(wèn)每只貓咪有多少顆花生？

【題解】：m達(dá)到10^9，顯然不能直接算。
              因?yàn)閗個(gè)操作給出之后就是固定的，所以想到用矩陣，矩陣快速冪可以把時(shí)間復(fù)雜度降到O（logm）。問(wèn)題轉(zhuǎn)化為如何構(gòu)造轉(zhuǎn)置矩陣？
              說(shuō)下我的思路，觀察以上三種操作，發(fā)現(xiàn)第二，三種操作比較容易處理，重點(diǎn)落在第一種操作上。
              有一個(gè)很好的辦法就是添加一個(gè)輔助，使初始矩陣變?yōu)橐粋€(gè)n+1元組，編號(hào)為0到n，下面以3個(gè)貓為例：
              定義初始矩陣A = [1 0 0 0]，0號(hào)元素固定為1，1~n分別為對(duì)應(yīng)的貓所擁有的花生數(shù)。
              對(duì)于第一種操作g i，我們?cè)趩挝痪仃嚮A(chǔ)上使Mat[0][i]變?yōu)?，例如g 1：
              1 1 0 0
              0 1 0 0
              0 0 1 0
              0 0 0 1，顯然[1 0 0 0]*Mat = [1 1 0 0]
              對(duì)于第二種操作e i，我們?cè)趩挝痪仃嚮A(chǔ)使Mat[i][i] = 0,例如e 2：
              1 0 0 0
              0 1 0 0
              0 0 0 0
              0 0 0 1, 顯然[1 2 3 4]*Mat = [1 2 0 4]
              對(duì)于第三種操作s i j，我們?cè)趩挝痪仃嚮A(chǔ)上使第i列與第j互換，例如s 1 2：
              1 0 0 0
              0 0 0 1
              0 0 1 0
              0 1 0 0，顯然[1 2 0 4]*Mat = [1 4 0 2]
              現(xiàn)在，對(duì)于每一個(gè)操作我們都可以得到一個(gè)轉(zhuǎn)置矩陣，把k個(gè)操作的矩陣相乘我們可以得到一個(gè)新的轉(zhuǎn)置矩陣T。
              A * T 表示我們經(jīng)過(guò)一組操作，類似我們可以得到經(jīng)過(guò)m組操作的矩陣為 A * T ^ m,最終矩陣的[0][1~n]即為答案。

              上述的做法比較直觀，但是實(shí)現(xiàn)過(guò)于麻煩，因?yàn)橐獦?gòu)造k個(gè)不同矩陣。

              有沒(méi)有別的方法可以直接構(gòu)造轉(zhuǎn)置矩陣T？答案是肯定的。
              我們還是以單位矩陣為基礎(chǔ)：
              對(duì)于第一種操作g i，我們使Mat[0][i] = Mat[0][i] + 1；
              對(duì)于第二種操作e i，我們使矩陣的第i列清零；
              對(duì)于第三種操作s i j，我們使第i列與第j列互換。
              這樣實(shí)現(xiàn)的話，我們始終在處理一個(gè)矩陣，免去構(gòu)造k個(gè)矩陣的麻煩。

              至此，構(gòu)造轉(zhuǎn)置矩陣T就完成了，接下來(lái)只需用矩陣快速冪求出 A * T ^ m即可，還有一個(gè)注意的地方，該題需要用到long long。
              具體實(shí)現(xiàn)可以看下面的代碼。

【代碼】：