poj3233 http://poj.org/problem?id=3233
给定n ，k，m
然后是n*n行，
我们先可以把式子转化为递推的，然后就可以用矩阵来加速计算了。 矩阵是加速递推计算的一个好工具
我们可以看到，矩阵的每个元素都是一个矩阵，其实这计算一个分块矩阵，我们可以把分块矩阵展开，它的乘法和普通矩阵的乘法是一样的。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
#pragma warning(disable:4996)
typedef long long LL;
const int INF = << ;
int MOD;
/*
矩阵的元素是矩阵，即分块矩阵
分块矩阵的乘法和普通矩阵的乘法是一样的
*/
struct Matrix
{
int mat[][];
int size;
Matrix(int n)
{
size = n;
}
void makeZero()
{
for (int i = ; i < size; ++i)
{
for (int j = ; j < size; ++j)
mat[i][j] = ;
}
}
void makeUnit()
{
for (int i = ; i < size; ++i)
{
for (int j = ; j < size; ++j)
mat[i][j] = (i == j);
}
}
}; Matrix operator*(const Matrix &lhs, const Matrix &rhs)
{
Matrix ret(lhs.size);
ret.makeZero();
for (int i = ; i < lhs.size; ++i)
{
for (int j = ; j < lhs.size; ++j)
{
for (int k = ; k < lhs.size; ++k)
{
ret.mat[i][j] += (lhs.mat[i][k] * rhs.mat[k][j]);
if (ret.mat[i][j] >= MOD)
ret.mat[i][j] %= MOD;
}
}
}
return ret;
}
Matrix operator^(Matrix &a, int k)
{
Matrix ret(a.size);//单位矩阵
ret.makeUnit();
while (k)
{
if (k & )
{
ret = ret * a;
}
a = a * a;
k >>= ;
}
return ret;
}
int main()
{
int n, k, m, i, j;
while (scanf("%d%d%d", &n, &k, &MOD) != EOF)
{
Matrix a(*n);
Matrix tmp(*n);;
a.makeZero();
for (i = ; i < n; ++i)
{
for (j = ; j < n; ++j)
{
scanf("%d", &a.mat[i][j]);
if (a.mat[i][j] >= MOD)
a.mat[i][j] %= MOD;
tmp.mat[i][j] = a.mat[i][j];
tmp.mat[i][n + j] = a.mat[i][j];
}
a.mat[n + i][i] = a.mat[n + i][n + i] = ;
}
a = a ^ (k - );
Matrix ans(*n);
ans.makeZero();
m = * n;
for (i = ; i < n; ++i)
{
for (j = ; j < n; ++j)
{
for (k = ; k < m; ++k)
{
ans.mat[i][j] += tmp.mat[i][k] * a.mat[k][j];
if (ans.mat[i][j] >= MOD)
ans.mat[i][j] %= MOD;
}
}
}
for (i = ; i < n; ++i)
{
for (j = ; j < n; ++j)
{
j == n - ? printf("%d\n", ans.mat[i][j]) : printf("%d ", ans.mat[i][j]);
}
}
}
return ;
}
当然了，我们还可以用二分的方法方法来计算
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
#pragma warning(disable:4996)
typedef long long LL;
const int INF = << ;
int MOD;
/*
矩阵的元素是矩阵，即分块矩阵
分块矩阵的乘法和普通矩阵的乘法是一样的
*/
struct Matrix
{
int mat[][];
int size;
Matrix(int n)
{
size = n;
}
void makeZero()
{
for (int i = ; i < size; ++i)
{
for (int j = ; j < size; ++j)
mat[i][j] = ;
}
}
void makeUnit()
{
for (int i = ; i < size; ++i)
{
for (int j = ; j < size; ++j)
mat[i][j] = (i == j);
}
}
}; Matrix operator*(const Matrix &lhs, const Matrix &rhs)
{
Matrix ret(lhs.size);
ret.makeZero();
for (int i = ; i < lhs.size; ++i)
{
for (int j = ; j < lhs.size; ++j)
{
for (int k = ; k < lhs.size; ++k)
{
ret.mat[i][j] += (lhs.mat[i][k] * rhs.mat[k][j]);
if (ret.mat[i][j] >= MOD)
ret.mat[i][j] %= MOD;
}
}
}
return ret;
}
Matrix operator^(Matrix &a, int k)
{
Matrix ret(a.size);//单位矩阵
ret.makeUnit();
while (k)
{
if (k & )
{
ret = ret * a;
}
a = a * a;
k >>= ;
}
return ret;
}
Matrix operator+(const Matrix &lhs, const Matrix &rhs)
{
Matrix ret(lhs.size);
ret.makeZero();
for (int i = ; i < lhs.size; ++i)
{
for (int j = ; j < lhs.size; ++j)
{
ret.mat[i][j] = lhs.mat[i][j] + rhs.mat[i][j];
if (ret.mat[i][j] >= MOD)
ret.mat[i][j] %= MOD;
}
}
return ret;
}
Matrix matrixSum(Matrix a, int k)
{
if (k == )
return a;
Matrix ret = matrixSum(a, k / );
if (k & )
{
Matrix tmp = a ^ (k / + );
ret = ret * tmp + ret + tmp;
}
else
{
Matrix tmp = a ^ (k / );
ret = ret*tmp + ret;
}
return ret;
}
int main()
{
int n, k, m, i, j;
while (scanf("%d%d%d", &n, &k, &MOD) != EOF)
{
Matrix a(n);
for (i = ; i < n; ++i)
{
for (j = ; j < n; ++j)
{
scanf("%d", &a.mat[i][j]);
if (a.mat[i][j] >= MOD)
a.mat[i][j] %= MOD;
}
}
Matrix ans = matrixSum(a, k);
for (i = ; i < n; ++i)
{
for (j = ; j < n; ++j)
j == n - ? printf("%d\n", ans.mat[i][j]) : printf("%d ", ans.mat[i][j]);
}
return ;
}
}