【循环矩阵+矩阵快速幂】Cellular Automaton UVA - 1386

Think:
1知识点：循环矩阵+矩阵快速幂
2题意：输入n(1<=n<=500), m(1<=n<=1000000), d(0<=d<(n/2)), k(1<=k<=10000000)然后输入一个n个数的环，数的范围为[0,m-1]，然后进行k次变换，变换为：取环中当前元素，然后取其左边d个数，取其右边d个数，然后相加取模m，询问经过k次变换之后的序列
3题意思考：
（１）：写出系数矩阵，会发现系数矩阵n*n太大，空间复杂度和时间复杂度都相对过大，进而通过循环矩阵性质，将空间复杂度由二维矩阵优化至一维矩阵，矩阵乘法的时间复杂度由n^3优化至n^2
4反思：
（１）：函数形参传入为常变量时，无法在函数内改变传入的常变量的值
（２）：矩阵运算的性质以及特殊矩阵的性质需要复习回顾

以下为Accepted代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
LL mod;
struct Matrix{
LL v[504];
};
Matrix multiply(const Matrix &a, const Matrix &b, int Matrix_len);
Matrix matrix_pow(Matrix x, int k, int Matrix_len);
LL rec[504], ans[504];
int main(){
int n, d, k, i, j;
while(~scanf("%d %lld %d %d", &n, &mod, &d, &k)){
Matrix x;
for(i = 0; i < n; i++)
scanf("%lld", &rec[i]);
memset(x.v, 0, sizeof(x.v));
x.v[0] = 1;
for(i = 1; i <= d; i++){
x.v[i] = 1;
}
for(i = n-1; i >= n-d; i--){
x.v[i] = 1;
}
Matrix y = matrix_pow(x, k-1, n);
memset(ans, 0, sizeof(ans));
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
ans[i] += y.v[(j-i+n)%n]*rec[j];
ans[i] %= mod;
}
}
for(i = 0; i < n; i++)
printf("%lld%c", ans[i], i == n-1? 'n': ' ');
}
return 0;
}
Matrix multiply(const Matrix &a, const Matrix &b, int Matrix_len){
Matrix tmp;
memset(tmp.v, 0, sizeof(tmp.v));
for(int i = 0; i < Matrix_len; i++){
for(int j = 0; j < Matrix_len; j++){
tmp.v[i] += a.v[j]*b.v[(i-j+Matrix_len)%Matrix_len];
tmp.v[i] %= mod;
}
}
return tmp;
}
Matrix matrix_pow(Matrix x, int k, int Matrix_len){
Matrix tmp = x;
while(k){
if(k & 1)
tmp = multiply(tmp, x, Matrix_len);
x = multiply(x, x, Matrix_len);
k >>= 1;
}
return tmp;
}

最后

以上就是眼睛大黑米为你收集整理的【循环矩阵+矩阵快速幂】Cellular Automaton UVA - 1386的全部内容，希望文章能够帮你解决【循环矩阵+矩阵快速幂】Cellular Automaton UVA - 1386所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。