题目链接:Click here~~
题意:
给你一个n*n的矩阵 A,求出 A + A^2 + … + A^k 的值。
解题思路:
需用用到两次二分。
考虑 k 为奇数和偶数两种情况。
1、奇数:A + A^2 + … + A^k = 【A + A^2 + … + A^(k/2)】 + A^(k/2+1) + A^(k/2+1)*【A + A^2 + … + A^(k/2)】。
2、偶数:A + A^2 + … + A^k = 【A + A^2 + … + A^(k/2)】 + A^(k/2)*【A + A^2 + … + A^(k/2)】。
其中,A^(k/2) 和 A^(k/2+1) 与 【A + A^2 + … + A^k 】的值可以通过二分算出。
#include <stdio.h>
#include <string.h>
typedef __int64 LL;
#define N 32
int K,mod;
struct Matrix
{
int r,c;
int m[N][N];
Matrix(){}
Matrix(int r,int c):r(r),c(c){}
Matrix operator *(const Matrix& B)
{
Matrix T(r,B.c);
for(int i=1;i<=T.r;i++)
{
for(int j=1;j<=T.c;j++)
{
int tt = 0;
for(int k=1;k<=c;k++)
tt += m[i][k]*B.m[k][j] % mod;
T.m[i][j] = tt % mod;
}
}
return T;
}
Matrix operator +(const Matrix& B)
{
Matrix T(r,c);
for(int i=1;i<=T.r;i++)
for(int j=1;j<=T.c;j++)
T.m[i][j] = (m[i][j]+B.m[i][j]) % mod;
return T;
}
Matrix Unit(int h)
{
Matrix T(h,h);
memset(T.m,0,sizeof(T.m));
for(int i=1;i<=h;i++)
T.m[i][i] = 1;
return T;
}
Matrix Pow(int n)
{
Matrix P = *this,Res = Unit(r);
while(n)
{
if(n&1)
Res = Res*P;
P = P*P;
n >>= 1;
}
return Res;
}
void Init()
{
int h;
scanf("%d%d%d",&h,&K,&mod);
r = c = h;
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
scanf("%d",&m[i][j]);
}
void Print()
{
for(int i=1;i<=r;i++)
{
for(int j=1;j<=c;j++)
printf("%d ",m[i][j]);
printf("\n");
}
}
}Single;
Matrix solve(int k)
{
if(k == 1)
return Single;
Matrix Sum = solve(k/2);
if(k&1)
{
Matrix Ak_1 = Single.Pow(k/2+1);
return Sum + Ak_1 + Ak_1*Sum;
}
else
{
Matrix Ak = Single.Pow(k/2);
return Sum + Ak*Sum;
}
}
int main()
{
Single.Init();
Matrix Ans(Single.r,Single.c);
Ans = solve(K);
Ans.Print();
return 0;
}
分享到:
相关推荐
北大POJ2109-Power of Cryptography 解题报告+AC代码
北大POJ1459-Power Network 解题报告+AC代码
poj3233的代码,利用了面向对象的编程,是复习C++知识的好例子
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
北大POJ1001-Precision power 解题报告+AC代码
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ初级-所有题目AC代码+解题报告
POJ2186-Popular Cows 【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 1459 Power Network.md
北大POJ1584-A Round Peg in a Ground Hole 解题报告+AC代码
北大POJ2586-Y2K Accounting Bug 解题报告+AC代码
北大POJ1691-Painting A Board 【拓扑+DFS】 解题报告+AC代码
北大POJ2031-Building a Space Station【Prim+计算几何】 POJ2031-Building a Space Station【Prim+计算几何】
NULL 博文链接:https://128kj.iteye.com/blog/1754756
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ初级-简单搜索 解题报告+AC代码
北大POJ1159-Palindrome 解题报告+AC代码