[SPOJ SPP] Recursive Sequence (Version II) 矩阵加速

本文主要是介绍[SPOJ SPP] Recursive Sequence (Version II) 矩阵加速，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

如果不求和这道题就变成了UVA10870(以前发过，不多说) 加入求和后就需要更改之前的矩阵了

首先保存有关项是必要的 这关系到递推的进行 但是需要额外加入一项 那就是前N项和 这个何又上一次的前N项和 + 前面存下来的相关项乘系数相加得到 例如Fib数列 构造如下矩阵

1            1             2

第一项   第二项    和

那么得到他的计算矩阵

0            1           1

1            1           1

0            0           1

继承相关项     计算新项          计算新的和

得到这样的矩阵后便可解决此题了 需要注意的是我之前写的乘法是利用函数返回答案 这样导致了这道题的超时 所以我改为了直接在函数内部赋值

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
#define MAXN 15
#define MAXM 15
typedef long long LL;
struct Matrix{  int n, m;  LL A[MAXN+10][MAXN+10];  
};
LL a[MAXN], f[MAXN];
int d;
LL p;
const LL INF = 10000000000LL;
Matrix A, B, E, Z;
void init(Matrix &X)
{X.n = X.m = 0;memset(X.A, 0, sizeof(X.A));
}
void Get_E()
{E.n = E.m = MAXN;for(int i = 0; i < E.n; i++) E.A[i][i] = 1;
}
Matrix add(Matrix AA, Matrix BB)
{Matrix D; D = AA;for(int i = 0; i < AA.n; i++)for(int j = 0; j < AA.m; j++){D.A[i][j] += BB.A[i][j];D.A[i][j] %= p;}return D;
}
void mul(Matrix AA, Matrix BB, Matrix &Ans)
{Matrix D;init(D);Ans.n = D.n = AA.n;Ans.m = D.m = BB.m;for(int i = 0; i < AA.n; i++)for(int j = 0; j < BB.n; j++)for(int k = 0; k < BB.m; k++){D.A[i][k] += (AA.A[i][j] * BB.A[j][k]) % p;D.A[i][k] %= p;}memcpy(Ans.A, D.A, sizeof(D.A));
}
Matrix pow_mod(Matrix &A, LL k)
{Matrix ans = E, t = A;ans.n = A.n;ans.m = A.m;while(k){if(k & 1)mul(ans, t, ans);mul(t, t, t);k >>= 1;}return ans;
}
int main()
{ios::sync_with_stdio(false);Get_E();init(Z);int kase;cin >> kase;while(kase--)          // A 初始矩阵 B 构造的矩阵{LL st, ed;cin >> d;d++;init(A); init(B); for(int i = 0; i < d-1; i++) cin >> a[i];for(int i = 0; i < d-1; i++) cin >> f[i];for(int i = 0; i < (d-1-i-1); i++) swap(f[i], f[d-i-2]);cin >> st >> ed >> p;A.n = 1;A.m = d;Z.n = Z.m = E.n = E.m = B.n = B.m = d;LL FN = 0, FM = 0;for(int i = 0; i < d-1; i++)B.A[i][d-2] = B.A[i][d-1] = f[i];for(int i = 1; i < d-1; i++) B.A[i][i-1] = 1;B.A[d-1][d-1] = 1;for(int i = 0; i < d-1; i++){A.A[0][i] = a[i];A.A[0][d-1] = (A.A[0][d-1] + a[i]) % p;}if(ed <= d){for(int i = st; i <= ed; i++) FM = (FM + a[i]) % p;cout << FM << '\n';continue;}if(st >= d){Matrix Tmp = pow_mod(B, st-d);mul(A, Tmp, Tmp);FN = Tmp.A[0][d-1];Tmp = pow_mod(B, ed-d+1);mul(A, Tmp, Tmp);FM = Tmp.A[0][d-1];cout << (FM - FN + p) % p << '\n';continue;}else{for(int i = 0; i < st-1; i++) FM -= a[i];Matrix Tmp = pow_mod(B, ed-d+1);mul(A, Tmp, Tmp);FM += Tmp.A[0][d-1];cout << FM % p << '\n';continue;}}
}

这篇关于[SPOJ SPP] Recursive Sequence (Version II) 矩阵加速的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---