So Easy!
题面


题意
给一个n然后利用公式求出S(n)的值
分析
这是一道矩阵快速幂的模板题目
我们设 ( a + b ) n = x + y b ( a 1 ) 2 &lt; b &lt; a 2 (a+√b)^{n}=x+y√b 其中(a-1) ^{2}&lt; b &lt; a^{ 2} (a+b)n=x+yb(a1)2<b<a2,那么ceil(√b)=a;我们可以知道 ( a + b ) n = x n + y n b = ( a + b ) n 1 ( a + b ) = ( x n . . 1 + y n . . 1 b ) ( a + b ) = ( x n . . 1 a + y n . . 1 b ) + ( a y n . . 1 + x n . . 1 ) b , (a+√b)^{n}=x_n+y_n√b=(a+√b)^{n-1}*(a+√b)=(x_n._-._1+y_n._-._1√b)*(a+√b)=(x_n._-._1∗a+y_n._-._1b)+(a∗y_n._-._1+x_n._-._1)∗√b,这时,我们就可以得到一个递归式,而且这个递归式可以用矩阵行列式表示, (a+b)n=xn+ynb=(a+b)n1(a+b)=(xn..1+yn..1b)(a+b)=(xn..1a+yn..1b)+(ayn..1+xn..1)b,
AC代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll a,m,b,n;
struct martix{
	ll mo[3][3];
	martix(){
		memset(mo,0,sizeof(mo));
	}
};///定义一种新的结构类型(矩阵)
martix mul(martix a,martix b){
	martix c;
        for(ll i=1;i<=2;i++){
		for(ll j=1;j<=2;j++){
			for(ll k=1;k<=2;k++){
			c.mo[i][j]=(c.mo[i][j]+a.mo[i][k]*b.mo[k][j])%m;
			}
		}
        }
        return c;
}///计算二阶与二阶的行列式相乘
martix powmo(martix al,ll n){
  martix T;
	        T.mo[1][1]=1;
		T.mo[2][2]=1;///初始化为单位矩阵
	while(n){
		if(n&1){
			T=mul(al,T);
		}
		n>>=1;
		al=mul(al,al);
	}
	return T;
}///计算行列式al的n次方
int main(){
	while(cin>>a>>b>>n>>m) {
		martix q;
		q.mo[1][1]=a;q.mo[1][2]=b;
	        q.mo[2][1]=1;q.mo[2][2]=a;
		martix res=powmo(q,n);
		cout<<(2*res.mo[1][1])%m<<endl;
	}
	return 0;
}