HDU 5950 Recursive sequence

2019-11-08 18:23:51

字体：大中小

来源：转载

供稿：网友

HDU 5950 Recursive sequence

矩阵快速幂构造

传送门：HustOJ

传送门：HDU

题意

已知递推公式：F(n) = 2*F(n-2) + F(n-1) + n4 和F(1) = a，F(2) = b；给定一个N，求F(N)等于多少？

思路

膜吧，%%%。

由于N很大，直接递推肯定超时，所以要用到矩阵快速幂的知识log(n)的复杂度来解决。问题的关键就在于如何构造矩阵上，可以看出本题的递推公式是一个非线性的式子，所以要将非线性的部分展开为线性的。

这里写图片描述

代码

因为mod那个const定义成了int而wa，我也是醉了

#include <cstdio>#include <cstdlib>#include <iostream>#include <algorithm>#include <string>#include <cstring>#include <vector>#include <cmath>#include <queue>#include <stack>#define _ ios_base::sync_with_stdio(0);cin.tie(0);#define M(a,b) memset(a,b,sizeof(a));using namespace std;const int MAXN=8;const int oo=0x3f3f3f3f;typedef long long LL;const LL loo=4223372036854775807ll;typedef long double LB;const LL mod=2147493647;struct Matrix{ LL ma[7][7]; Matrix() { M(ma, 0); } Matrix(Matrix &m) { for(int i=0;i<7;i++) for(int j=0;j<7;j++) ma[i][j]=m.ma[i][j]; } Matrix Operator * (Matrix m) { Matrix res; for(int i=0;i<7;i++) { for(int j=0;j<7;j++) { res.ma[i][j]=( (ma[i][0]*m.ma[0][j])%mod+ (ma[i][1]*m.ma[1][j])%mod+ (ma[i][2]*m.ma[2][j])%mod+ (ma[i][3]*m.ma[3][j])%mod+ (ma[i][4]*m.ma[4][j])%mod+ (ma[i][5]*m.ma[5][j])%mod+ (ma[i][6]*m.ma[6][j])%mod)%mod; } } return res; } Matrix operator ^ (int n) { Matrix res; Matrix tmp=(*this); for(int i=0;i<7;i++) res.ma[i][i]=1; while(n) { if(n%2) { res=res*tmp; } n=n/2; tmp=tmp*tmp; } return res; }};int main(){ _ int T;cin>>T; while(T--) { LL n, a, b; cin>>n>>a>>b; Matrix ma; ma.ma[0][1]=1; ma.ma[1][0]=2, ma.ma[1][1]=1, ma.ma[1][2]=1, ma.ma[1][3]=4, ma.ma[1][4]=6, ma.ma[1][5]=4, ma.ma[1][6]=1; ma.ma[2][2]=1, ma.ma[2][3]=4, ma.ma[2][4]=6, ma.ma[2][5]=4, ma.ma[2][6]=1; ma.ma[3][3]=1, ma.ma[3][4]=3, ma.ma[3][5]=3, ma.ma[3][6]=1; ma.ma[4][4]=1, ma.ma[4][5]=2, ma.ma[4][6]=1; ma.ma[5][5]=ma.ma[5][6]=ma.ma[6][6]=1; if(n==1) cout<<a%mod<<endl; else if(n==2) cout<<b%mod<<endl; else { Matrix res; res=ma.operator^(n-2); LL ttt=((res.ma[1][0]*a)%mod+ (res.ma[1][1]*b)%mod+ (res.ma[1][2]*16)%mod+ (res.ma[1][3]*8)%mod+ (res.ma[1][4]*4)%mod+ (res.ma[1][5]*2)%mod+ (res.ma[1][6]*1)%mod)%mod; cout<<ttt<<endl; } } return 0;}

上一篇：图结构练习——最短路径

下一篇：ISP算法系统概念