给你一个一维细胞自动机,第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;
}

最新文章

  1. polya/burnside 学习
  2. Fiddler-1 安装
  3. Wijmo 2016 V1 强势发布,全面支持Angular 2
  4. HttpContext.Current.Cache 和HttpRuntime.Cache的区别
  5. no branch 问题
  6. iOS - UITextView
  7. Sublime text3使用技巧及快捷键
  8. .net MVC开源项目分享(1) 项目的基本情况
  9. angularjs 怎么获取鼠标焦点 鼠标移入显示浮动的div提示框
  10. Django教程01-全流程
  11. AJAX请求方式
  12. centos6.5 squid安装
  13. 微信、支付宝支付SDK
  14. 微信小程序开发(2) 计算器
  15. python pop方法
  16. 自己手写一个queuelink
  17. 云笔记项目-笔记列表弹出&quot;分享移动删除&quot;子菜单
  18. 火热的线上APP的源码分享,开箱即用
  19. python - class类 (二) 静态属性/类方法/静态方法
  20. day 69 权限的设置

热门文章

  1. 【HNOI】矩阵染色 数论
  2. linux编程之文件操作
  3. qt-creator
  4. PXC 避免加入集群时发生SST
  5. C#利用WinRAR实现压缩和解压缩
  6. MiCode108 猜数字
  7. elasticsearch索引加别名
  8. 都是干货---真正的了解scrapy框架
  9. Markdown语法简编
  10. Internet Explorer 浏览器在同一时刻只能从同一域名下载两个文件。