傳送門：HustOJ
傳送門：HDU
已知遞推公式：F(n) = 2*F(n-2) + F(n-1) + n4 和F(1) = a，F(xiàn)(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;}新聞熱點
疑難解答
