Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
贴一个一般般的代码#include <iostream> using namespace std; struct Matrix//矩阵 { int e[30][30];//矩阵的元素 }; Matrix powF[32][2][2];//存储初始矩阵的 1 到 31 次幂 (powF[0] 均为零矩阵) void mult(Matrix * x, Matrix * y, Matrix * res, int & n, int & m);//(n 阶矩阵对 m 取模) 把 x * y 输出至 res void add(Matrix * x, Matrix * y, Matrix * res, int & n, int & m);//(n 阶矩阵对 m 取模) 把 x + y 输出至 res void cpy(Matrix * tar, Matrix * x, int & n);//(n 阶矩阵) 把 x 拷贝至 tar void output(Matrix * x, int & n);//打印 n 阶矩阵 x int main() { int n, k, m, t; Matrix sumA, tA, tF[2][2], ansF[2][2]; cin >> n >> k >> m; k++;//需要计算矩阵的 k + 1 次幂 for (int k1 = 0; k1 < 2; k1++) { for (int k2 = 0; k2 < 2; k2++) { cpy(&ansF[k1][k2], &powF[0][0][0], n); } } for (int k1 = 0; k1 < n; k1++) { for (int k2 = 0; k2 < n; k2++) { cin >> t; powF[1][0][0].e[k1][k2] = t % m; } powF[1][1][0].e[k1][k1] = 1; powF[1][1][1].e[k1][k1] = 1; ansF[0][0].e[k1][k1] = 1; ansF[1][1].e[k1][k1] = 1; } //计算初始矩阵的 2 到 31 次幂 for (int i = 2; i < 32; i++) { for (int k1 = 0; k1 < 2; k1++) { for (int k2 = 0; k2 < 2; k2++) { cpy(&sumA, &powF[0][0][0], n); for (int j = 0; j < 2; j++) { mult(&powF[i - 1][k1][j], &powF[i - 1][j][k2], &tA, n, m); add(&sumA, &tA, &sumA, n, m); } cpy(&tF[k1][k2], &sumA, n); } } for (int k1 = 0; k1 < 2; k1++) { for (int k2 = 0; k2 < 2; k2++) { cpy(&powF[i][k1][k2], &tF[k1][k2], n); } } } int p = 0; while (k) { p++; if (k & true) { for (int k1 = 0; k1 < 2; k1++) { for (int k2 = 0; k2 < 2; k2++) { cpy(&sumA, &powF[0][0][0], n); for (int j = 0; j < 2; j++) { mult(&powF[p][k1][j], &ansF[j][k2], &tA, n, m); add(&sumA, &tA, &sumA, n, m); } cpy(&tF[k1][k2], &sumA, n); } } for (int k1 = 0; k1 < 2; k1++) { for (int k2 = 0; k2 < 2; k2++) { cpy(&ansF[k1][k2], &tF[k1][k2], n); } } } k >>= 1; } cpy(&tA, &powF[0][0][0], n); for (int i = 0; i < n; i++) { tA.e[i][i] = m - 1;//防止出现负数 } add(&ansF[1][0], &tA, &ansF[1][0], n, m); output(&ansF[1][0], n); return 0; } //(n 阶矩阵对 m 取模) 把 x * y 输出至 res void mult(Matrix * x, Matrix * y, Matrix * res, int & n, int & m) { static Matrix tA; static int sum; for (int k1 = 0; k1 < n; k1++) { for (int k2 = 0; k2 < n; k2++) { sum = 0; for (int j = 0; j < n; j++) { sum += x->e[k1][j] * y->e[j][k2]; } tA.e[k1][k2] = sum % m; } } for (int k1 = 0; k1 < n; k1++) { for (int k2 = 0; k2 < n; k2++) { res->e[k1][k2] = tA.e[k1][k2]; } } return; } //(n 阶矩阵对 m 取模) 把 x + y 输出至 res void add(Matrix * x, Matrix * y, Matrix * res, int & n, int & m) { static Matrix tA; for (int k1 = 0; k1 < n; k1++) { for (int k2 = 0; k2 < n; k2++) { tA.e[k1][k2] = x->e[k1][k2] + y->e[k1][k2]; } } for (int k1 = 0; k1 < n; k1++) { for (int k2 = 0; k2 < n; k2++) { res->e[k1][k2] = tA.e[k1][k2] % m; } } return; } //(n 阶矩阵) 把 x 拷贝至 tar void cpy(Matrix * tar, Matrix * x, int & n) { for (int k1 = 0; k1 < n; k1++) { for (int k2 = 0; k2 < n; k2++) { tar->e[k1][k2] = x->e[k1][k2]; } } return; } //打印 n 阶矩阵 x void output(Matrix * x, int & n) { for (int k1 = 0; k1 < n; k1++) { for (int k2 = 0; k2 < n; k2++) { cout << x->e[k1][k2] << ' '; } cout << '\n'; } return; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator