国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

矩陣快速冪 非詳解

2019-11-14 08:59:18
字體：大 中 小
來源：轉載
供稿：網友
#include <cstdio>#include <cstring>int n, k;const int mod = 9973;struct matrix{ int tr[10][10]; matrix Operator * (const matrix &a) const{//重載運算符 matrix tmp; memset(tmp.tr, 0, sizeof(tmp.tr)); for(int i = 0; i < n; i++) for(int j = 0; j < n; j++){ for(int k = 0; k < n; k++) tmp.tr[i][j] += tr[i][k] * a.tr[k][j]; tmp.tr[i][j] %= mod;//這里要取模，不然可能溢出 } return tmp; }}ans, ori;matrix pow_mod(int k){ for(int i = 0; i < n; i++) ans.tr[i][i] = 1;//化為單位矩陣 while(k){ if(k&1) ans = ans*ori;//不能寫成ans *= ori，因為沒有重載*=運算符 k >>= 1; ori = ori*ori; }//核心代碼，下面有解釋}int main(){ int t; scanf("%d", &t); while(t--){ scanf("%d%d", &n, &k); memset(ans.tr, 0, sizeof(ans.tr)); memset(ori.tr, 0, sizeof(ori.tr)); for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) scanf("%d", &ori.tr[i][j]); pow_mod(k); long long res = 0; for(int i = 0; i < n; i++){ res += ans.tr[i][i] % mod; } 核心代碼：

while(k){ if(k&1) ans = ans*ori; k >>= 1; ori = ori*ori; }

假設 k = 89，其二進制為 1011001， 顯然 a^k = ( a^1 ) * ( a^8 ) * ( a^16 ) * ( a^64 ); 也就是，k的二進制位為0時，可以跳過（右移） 。

每次判斷k的最后一位二進制位，若為1，則 ans = ans*ori ， 然后k右移一位，ori 乘以本身。

發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板： 西乌珠穆沁旗| 临朐县| 漳州市| 古交市| 高陵县| 张家口市| 疏勒县| 博湖县| 瑞丽市| 邵阳市| 彭泽县| 满城县| 霍城县| 三原县| 蒙阴县| 高邮市| 兴义市| 乌鲁木齐市| 南雄市| 平罗县| 缙云县| 商南县| 靖江市| 金塔县| 永吉县| 钟山县| 夹江县| 阳江市| 湖北省| 汉寿县| 建湖县| 永宁县| 溆浦县| 灯塔市| 陵水| 绿春县| 洱源县| 雷州市| 岱山县| 土默特左旗| 龙岩市|