| ||||||||||
| 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