【矩阵乘法】Gym - 101412C - One-Dimensional Cellular Automaton
2024-08-29 18:43:13
给你一个一维细胞自动机,第i个格子在时刻t的状态是这样获得的,问你t时刻的状态。
把0时刻的状态视作一个列向量,发现状态转移其实是一个n*n的矩阵(以n=5为例),
B | C | |||
A | B | C | ||
A | B | C | ||
A | B | C | ||
A | B |
直接快速幂即可。
#include<cstdio>
#include<vector>
using namespace std;
typedef vector<int> vec;
typedef vector<vec> mat;
int n,m,A,B,C,T;
mat operator * (const mat &A,const mat &B){
mat C(A.size(),vec(B[0].size()));
for(int i=0;i<A.size();++i){
for(int k=0;k<B.size();++k){
for(int j=0;j<B[0].size();++j){
C[i][j]=(C[i][j]+A[i][k]*B[k][j])%m;
}
}
}
return C;
}
mat I;
mat Quick_Pow(mat a,int p){
if(!p){
return I;
}
mat res=Quick_Pow(a,p>>1);
res=res*res;
if(p&1){
res=res*a;
}
return res;
}
int main(){
// freopen("c.in","r",stdin);
while(1){
scanf("%d%d%d%d%d%d",&n,&m,&A,&B,&C,&T);
if(!n && !m && !A && !B && !C && !T){
return 0;
}
mat P(n,vec(1));
int x;
for(int i=0;i<n;++i){
scanf("%d",&x);
P[i][0]=x;
}
I.assign(n,vec(n));
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
I[i][j]=(i==j);
}
}
mat R(n,vec(n));
for(int i=0;i<n;++i){
if(i-1>=0){
R[i][i-1]=A;
}
R[i][i]=B;
if(i+1<n){
R[i][i+1]=C;
}
}
mat ans=Quick_Pow(R,T)*P;
for(int i=0;i<n-1;++i){
printf("%d ",ans[i][0]);
}
printf("%d\n",ans[n-1][0]);
}
return 0;
}
最新文章
- polya/burnside 学习
- Fiddler-1 安装
- Wijmo 2016 V1 强势发布,全面支持Angular 2
- HttpContext.Current.Cache 和HttpRuntime.Cache的区别
- no branch 问题
- iOS - UITextView
- Sublime text3使用技巧及快捷键
- .net MVC开源项目分享(1) 项目的基本情况
- angularjs 怎么获取鼠标焦点 鼠标移入显示浮动的div提示框
- Django教程01-全流程
- AJAX请求方式
- centos6.5 squid安装
- 微信、支付宝支付SDK
- 微信小程序开发(2) 计算器
- python pop方法
- 自己手写一个queuelink
- 云笔记项目-笔记列表弹出";分享移动删除";子菜单
- 火热的线上APP的源码分享,开箱即用
- python - class类 (二) 静态属性/类方法/静态方法
- day 69 权限的设置