POJ 3233 Matrix Power Series (矩阵分块,递推)
2024-08-24 21:32:18
矩阵乘法是可以分块的,而且幂的和也是具有线性的。
不难得到 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 ;
}
最新文章
- PHP try catch
- JSon_零基础_007_将JSon格式的";数组";字符串转换为Java对象";数组";
- c++中引用和指针的区别
- 利用UIImagePickerController或者利用UIKit的 UIGraphicsBeginImageContext保存图片
- 【转】android的startActivityForResult学习心得
- 在Eclipse中格式化Android代码
- (Relax 水题1.2)POJ 1032 Parliament(将n分解成若干个互不相等的整数的和,并且是这些整数的乘积最大)
- Lesson 4: Know Your Tools
- 数组初始化(c, c++, gcc, g++)
- 面试题:实现一个方法clone;可以对js五种数据类型进行值复制
- 值得一提:关于 HDFS 的 file size 和 block size
- 微软Tech Summit 2017,等你来打Call
- 如何编写高质量JavaScript代码
- 容器化时代我们应当选择Kubernetes
- spring的历史和设计科学
- @Html.Partial 和 @Html.RenderPartial 异同
- nmap脚本使用总结
- disruptor 高性能之道
- Layui_Tree模块遍历HDFS
- [数据结构与算法分析(Mark Allen Weiss)]二叉树的插入与删除 @ Python
热门文章
- 初始Java虚拟机
- (转)System.Web.Mvc.UrlHelper的学习与使用
- 我的省选 Day -12
- Scrapy框架中的Pipeline组件
- PHPExcel探索之旅---阶段四 导入文件
- 关于强大的requests
- CompareToBuilder构建Comparator
- spark_spark连接hive config
- LCS(Longest Common Subsequence)
- qemu 出现Could not access KVM kernel module: No such file or directory failed to initialize KVM: No such file or directory