题目链接
借鉴别人的一张解题思路
转化成了 (a^n + b^n) %M
#include<iostream> #include<string> #include<vector> #include<algorithm> #include<queue> #include<cstdio> #include<cstring> #include<cmath> #include<map> using namespace std; typedef long long ll; ll MOD ; struct Matrix { ll a[2][2]; Matrix() { memset(a, 0, sizeof(a)); } Matrix operator * (const Matrix y) { Matrix ans; for(int i = 0; i <= 1; i++) for(int j = 0; j <= 1; j++) for(int k = 0; k <= 1; k++) ans.a[i][j] += a[i][k]*y.a[k][j]; for(int i = 0; i <= 1; i++) for(int j = 0; j <= 1; j++) ans.a[i][j] %= MOD; return ans; } void operator = (const Matrix b) { for(int i = 0; i <= 1; i++) for(int j = 0; j <= 1; j++) a[i][j] = b.a[i][j]; } }; ll solve(ll a,ll b,ll n) { Matrix ans, trs; ans.a[0][1] = 1; //初始值 ans.a[0][0] = a; ans.a[0][1] = 2; // f(n) = a*f(n-1) + b * f(n-2); trs.a[0][0] = a; trs.a[1][0] = -b; trs.a[0][1] = 1; while(n) { if(n&1) ans = ans*trs; trs = trs*trs; n >>= 1; } return (ans.a[0][1]+ans.a[1][1]+MOD)%MOD;//improtant } int main() { ios_base::sync_with_stdio(false); // freopen("data.txt","r",stdin); ll aa,bb,m,n; while(cin>>aa>>bb>>n>>m) { ll p = 2*aa; ll q = aa*aa-bb; MOD = m; cout<<solve(p,q,n)<<endl; } return 0; }