矩阵乘法是可以分块的,而且幂的和也是具有线性的。

不难得到 Si = Si-1+A*Ai-1,Ai = A*Ai-1。然后矩阵快速幂就可以了。

/*********************************************************
* ------------------ *
* author AbyssalFish *
**********************************************************/
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<queue>
#include<vector>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<ctime>
using namespace std; typedef long long ll;
typedef vector<int> row;
typedef vector<row> mat; int n, k, M; mat Mul;
mat &operator *(mat &A, mat& B)
{
mat &R = Mul;
R.assign(n,row(n));
for(int i = ; i < n; i++){
for(int j = ; j < n; j++){
for(int k = ; k < n; k++){
R[i][j] = (R[i][j] +A[i][k]*B[k][j])%M; }
}
} return R;
} //#define LOCAL
#ifdef LOCAL
void censor(mat &B)
{
for(auto r: B){
for(int c: r)
cout<<c<<' ';
cout<<endl;
}
}
#endif mat operator ^(mat A,int q)
{
mat Re(n,row(n));
for(int i = ; i < n; i++) Re[i][i] = ;
while(q){
if(q&) Re = Re*A;
A = A*A;
q >>= ;
}
return Re;
} int main()
{
#ifdef LOCAL
freopen("in.txt","r",stdin);
#endif
int nn; scanf("%d%d%d",&nn,&k,&M);
n = *nn;
mat A(nn,row(nn));
for(int i = ; i < nn; i++){
for(int j = ; j < nn; j++){
scanf("%d",&A[i][j]);
}
}
mat B(n,row(n));
for(int i = ; i < nn; i++) {
B[i][i] = ;
copy(A[i].begin(),A[i].end(),B[i].begin()+nn);
copy(A[i].begin(),A[i].end(),B[i+nn].begin()+nn);
}
B = B^k;
for(int i = ; i < nn; i++){
for(int j = ; j < nn; j++){
printf("%d%c",B[i][j+nn],j==nn-?'\n':' ');
}
}
#ifdef LOCAL
cout<<"rum time:"<<clock()<<"ms"<<endl;
#endif // LOCAL
return ;
}

最新文章

  1. PHP try catch
  2. JSon_零基础_007_将JSon格式的&quot;数组&quot;字符串转换为Java对象&quot;数组&quot;
  3. c++中引用和指针的区别
  4. 利用UIImagePickerController或者利用UIKit的 UIGraphicsBeginImageContext保存图片
  5. 【转】android的startActivityForResult学习心得
  6. 在Eclipse中格式化Android代码
  7. (Relax 水题1.2)POJ 1032 Parliament(将n分解成若干个互不相等的整数的和,并且是这些整数的乘积最大)
  8. Lesson 4: Know Your Tools
  9. 数组初始化(c, c++, gcc, g++)
  10. 面试题:实现一个方法clone;可以对js五种数据类型进行值复制
  11. 值得一提:关于 HDFS 的 file size 和 block size
  12. 微软Tech Summit 2017,等你来打Call
  13. 如何编写高质量JavaScript代码
  14. 容器化时代我们应当选择Kubernetes
  15. spring的历史和设计科学
  16. @Html.Partial 和 @Html.RenderPartial 异同
  17. nmap脚本使用总结
  18. disruptor 高性能之道
  19. Layui_Tree模块遍历HDFS
  20. [数据结构与算法分析(Mark Allen Weiss)]二叉树的插入与删除 @ Python

热门文章

  1. 初始Java虚拟机
  2. (转)System.Web.Mvc.UrlHelper的学习与使用
  3. 我的省选 Day -12
  4. Scrapy框架中的Pipeline组件
  5. PHPExcel探索之旅---阶段四 导入文件
  6. 关于强大的requests
  7. CompareToBuilder构建Comparator
  8. spark_spark连接hive config
  9. LCS(Longest Common Subsequence)
  10. qemu 出现Could not access KVM kernel module: No such file or directory failed to initialize KVM: No such file or directory