LA 3704 Cellular Automaton (矩阵快速幂)

本文主要是介绍LA 3704 Cellular Automaton (矩阵快速幂)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

LA 3704 Cellular Automaton

题目大意:

一个环被分成n份,每个格子取值为0~m-1.给定距离d,则每次操作后每个格子的值为与其距离不超过d的格子操作前的值之和除以m的余数.
( $1\leq n \leq 500,1\leq m \leq 10^6,0\leq d < n/2,1\leq k \leq 10^7$ )

题目分析:

由题意可建立一个矩阵 $A$ ,使得 $F_k=A^kF$ ,显然可以用矩阵快速幂.
但是若采取朴素的快速幂,时间复杂度为 $O(d^3logk)$ .而 $n\leq 500$ ,时间复杂度可能过高.
观察可知矩阵 $A$ 的第i行实际是由第0行向右移动i个元素得到的,所以A其实可以压缩成一维,时间复杂度为 $O(d^2logk)$ .

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>using namespace std;typedef long long ll;
const int maxn=500+5;int MOD;struct Matrix {int n;ll M[maxn];Matrix(){memset(M,0,sizeof(M));n=0;}Matrix(int n):n(n){memset(M,0,sizeof(M));}Matrix operator * (const Matrix& rhs) const {Matrix ret(n);for(int i=0;i<n;i++) {for(int j=0;j<n;j++)//第i行的元素是由第0行从左往右移动了i个,所以A(i,j)=A(0,j-i) ret.M[i]+=M[j]*rhs.M[(j-i+n)%n];ret.M[i]%=MOD;}return ret;}Matrix operator *= (const Matrix& rhs) {return *this=*this*rhs;}
};Matrix qpow(Matrix x,int y)
{Matrix ret=x;if(--y==0) return x;while(y>0) {if(y&1) ret*=x;x*=x;y>>=1;}return ret;
}int main()
{int n,d,k;while(~scanf("%d%d%d%d",&n,&MOD,&d,&k)) {Matrix A(n),F(n);for(int i=0;i<n;i++) scanf("%lld",&F.M[i]);for(int i=0;i<n;i++) if(min(i,n-i)<=d) A.M[i]=1;A=qpow(A,k);F=F*A;printf("%lld",F.M[0]);for(int i=1;i<n;i++) printf(" %lld",F.M[i]);printf("\n");}return 0;
}