【题目链接】 ：click here~~
【题目大意】：
A sequence Snis defined as:
Where a, b, n, m are positive integers.┌x┐is the ceil of x. For example, ┌3.14┐=4. You are to calculate Sn. You, a top coder, say: So easy!
【解题思路】
给一张神图，推理写的灰常明白了，关键是构造共轭函数，，这一点实在是要有数学知识的理论基础，推出了递推式，接下来就是矩阵的快速幂了。
神图：click here~~
代码：
#include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>#include <math.h>using namespace std;#define LL long longLL MOD;struct Matrix{long long mapp[2][2];};Matrix unin= {1,0,0,1};//单位矩阵Matrix multi(Matrix a,Matrix b){Matrix c;for(int i=0; i<2; i++)for(int j=0; j<2; j++){c.mapp[i][j]=0;for(int k=0; k<2; k++)c.mapp[i][j]+=(a.mapp[i][k]*b.mapp[k][j])%MOD;c.mapp[i][j]%=MOD;}return c;}Matrix power(Matrix a,long long n)//矩阵快速幂{Matrix ans=unin;//单位矩阵Matrix res=a;while(n){if(n&1) ans=multi(ans,res);res=multi(res,res);n>>=1;}return ans;}int main(){LL A,B,N,M,ret;Matrix a,b;while(cin>>A>>B>>N>>MOD){a.mapp[0][0] = 2*A%MOD;//递推式a.mapp[0][1] = ((B%MOD-A*A%MOD)%MOD+MOD)%MOD;a.mapp[1][0] = 1;a.mapp[1][1] = 0;if(N==1){printf("%lld\n",2*A%MOD);continue;}b=power(a,N-1);ret=(b.mapp[0][0]%MOD*2*A%MOD+b.mapp[0][1]%MOD*2%MOD)%MOD;ret%=MOD;printf("%lld\n",ret);}return 0;}
夫妇一条心，泥土变黄金。
