从今天开始就有各站网络赛了
今天是ccpc全国赛的网络赛
希望一切顺利 可以去一次吉大 希望还能去一次大连
题意：
很明确是让你求Sn=[a+sqrt(b)^n]%m
思路：
一开始以为是水题 暴力了一发没过
上网看了一下才知道是快速幂
而且特征方程的推导简直精妙
尤其是共轭相抵消的构造 真的是太看能力了
（下图转自某大神博客）
特征方程是C^2=-2*a*C+(a*a-b)
然后用快速幂求解
临时学了下矩阵快速幂
从这道题能看出来
弄ACM真的要数学好
这不是学校认知的高数 线代 概率分数
而是一种数学思维
能想得到什么公式 会临场推导 这种能力才是最重要的
学校考试卷子上的分数只能证明你考试的能力
分数再高没有数学思维也是没用的
从这样的题才能看出来一个人的数学到底好不好
我的路还很远……
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<string>
#include<map>
#include<set>
#include<vector>
#include<queue>
#define M(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
ll m;
struct matrix{
ll mt[][];
matrix mul(matrix a,matrix b){ //矩阵相乘
matrix c;
M(c.mt,);
for(int i=;i<;i++)
for(int j=;j<;j++)
for(int k=;k<;k++)
c.mt[i][j]+=(a.mt[i][k]*b.mt[k][j])%m; //这里要模m 要不会因为溢出WA
return c;
}
matrix fast_pow(matrix a,ll mod){ //快速幂
matrix result;
for(int i=;i<;i++)
for(int j=;j<;j++)
result.mt[i][j]=(i==j);
while(mod){
if(mod%) result=mul(result,a);
a=mul(a,a);
mod/=;
}
return result;
}
}mt;
int main(){
ll a,b,n;
while(scanf("%I64d%I64d%I64d%I64d",&a,&b,&n,&m)!=EOF){
mt.mt[][]=*a;
mt.mt[][]=;
mt.mt[][]=b-a*a;
mt.mt[][]=;
mt=mt.fast_pow(mt,n-);
ll ans=((*a*mt.mt[][]+*mt.mt[][])%m+m)%m; //这里取两次模因为第一次取模可能是负数
printf("%I64d\n",ans);
}
return ;
}
/* 2 3 1 2013
2 3 2 2013
2 2 1 2013 */