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> #include<stack> #include<string.h> #include<cmath> #include<iomanip> #include<algorithm> #include<climits> #include<cstdio> #include<vector> #include<sstream> #include<ctype.h> #include<set> #include<map> #include<ctime> #include<stdlib.h> #include<queue> #include<bitset> #define ll long long #define inf INT_MAX using namespace std; template<typename TTT>inline void mr(TTT& theNumberToRead) { theNumberToRead = 0; bool prn = false; char c = getchar(); while (!isdigit(c)) { if (c == '-')prn = true; c = getchar(); } while (isdigit(c)) theNumberToRead = 10 * theNumberToRead + (c ^ 48), c = getchar(); if (prn) theNumberToRead = -theNumberToRead; } template<typename TTT>inline TTT mrr() { TTT theNumberToRead = 0; bool prn = false; char c = getchar(); while (!isdigit(c)) { if (c == '-')prn = true; c = getchar(); } while (isdigit(c)) theNumberToRead = 10 * theNumberToRead + (c ^ 48), c = getchar(); return prn ? -theNumberToRead : theNumberToRead; } template<typename T>void my_write(T x) { if (x) my_write(x / 10), putchar(x % 10 ^ 48); } template<typename T>void mw(T x, char mid) { if (x) { if (x < 0) putchar('-'), x = -x; my_write(x); } else putchar(48); if (mid) putchar(mid); } // ******************************************华丽的分割线****************************************** // ******************************************华丽的分割线****************************************** // ******************************************华丽的分割线****************************************** // ******************************************华丽的分割线****************************************** // ******************************************华丽的分割线****************************************** typedef vector<int> vec; typedef vector<vec> mat; int mod; mat mul(mat& a, mat& b) { mat c(a.size(), vec(b[0].size())); for (int i = 0; i < a.size(); ++i) for (int j = 0; j < b[0].size(); ++j) for (int k = 0; k < b.size(); ++k) c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod; return c; } mat fast_pow(mat a, int n) { mat b(a.size(), vec(a.size())); for (int i = 0; i < b.size(); ++i) b[i][i] = 1; while (n) { if (n & 1) b = mul(b, a); a = mul(a, a); n >>= 1; } return b; } int main() { int n, k; mr(n), mr(k), mr(mod); mat a(n << 1, vec(n << 1)); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) mr(a[i][j]), a[n + i][j] = a[i][j]; a[n + i][n + i] = 1; } a = fast_pow(a, k); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) mw(a[n + i][j], " \n"[j + 1 == n]); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator