HDU 4565 -- So Easy! （矩阵幂模板）

题目链接：hdu4565

题目要求这个得值

但是取模前有更号，所以无法直接计算，我们发现

0< a, m < 2¹⁵, (a-1)²< b < a², 0 < b, n < 2³¹

^{所以 0 <| a+sqrt( b ) | < 1}

可得表达式：，由二项式展开可知等号右边一坨是整数并且加的数小于一，所以等式成立

然后我们将 a+sqrt（b）看做一个整体，a-sqrt（b）看做一个整体，然后另p=a+sqrt（b）+a-sqrt（b）=2*a

q=（a+sqrt（b））*（a-sqrt（b））=a*a-b

接下来就与loj1070相同：博客

另Sn=（a+sqrt（b））^n+（a-sqrt（b））^n。

就可以求递推式 ：Sn=pS(n-1)-q*S(n-2)

即 （S2 S1）*（p  1）^(n-2)=(Sn S(n-2) )

                         -q   0

#include <cstdio> #include <cstring> #include <cmath> #include <iostream> using namespace std; typedef __int64 ll; #define N 3 // 这里开大了超时，原来开的32 int K,mod; struct Matrix { int r,c; ll m[N][N]; Matrix(){} Matrix(int r,int c):r(r),c(c){} Matrix operator *(const Matrix& B)//乘法 { Matrix T(r,B.c); for(int i=1;i<=T.r;i++) { for(int j=1;j<=T.c;j++) { ll tt = 0; for(int k=1;k<=c;k++) tt += m[i][k]*B.m[k][j] % mod; T.m[i][j] = tt % mod; } } return T; } Matrix Unit(int h) // 对角线矩阵 { Matrix T(h,h); memset(T.m,0,sizeof(T.m)); for(int i=1;i<=h;i++) T.m[i][i] = 1; return T; } Matrix Pow(int n) //矩阵幂 { Matrix P = *this,Res = Unit(r); while(n) { if(n&1) Res = Res*P; P = P*P; n >>= 1; } return Res; } void Print()//输出 { for(int i=1;i<=r;i++) { for(int j=1;j<=c;j++) printf("%d ",m[i][j]); printf("\n"); } } }Single; int main(){ ll a,b,n; while(cin >> a >> b >> n >> mod){ ll p=2*a%mod;// ll q=a*a%mod-b; Matrix cnt(2,2),ans(2,1); if(n==1){ cout << p << endl; continue; } ans.m[1][1] = p*p%mod-2*q; ans.m[2][1] = p; // 操作矩阵 cnt.m[1][1] = ans.m[2][1]; cnt.m[1][2] = (-q +mod)%mod; cnt.m[2][1] = 1; cnt.m[2][2] = 0; ans = cnt.Pow(n-2) * ans; cout << ans.m[1][1] << endl; } return 0; }