ACM集训之专题五： 构造共轭函数+矩阵快速幂 HDU 4565

题目

http://acm.hdu.edu.cn/showproblem.php?pid=4565
HDU 4565

A sequence S n is 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 S n.
　　You, a top coder, say: So easy!

Input
　　There are several test cases, each test case in one line contains four positive integers: a, b, n, m. Where 0< a, m < 2 15, (a-1) 2< b < a 2, 0 < b, n < 2 31.The input will finish with the end of file.
　　
Output
　　For each the case, output an integer S n.
　　
Sample Input
2 3 1 2013
2 3 2 2013
2 2 1 2013

Sample Output
4
14
4

题意

问你一个很大的底很大的超级大次幂。而且底数可能还是无理数，用普通的方法直接去算会超时，而且不一定精确。
这里要用到构造共轭函数以及矩阵快速幂的方法去做。

思路

分为两部分：
第一部分、构造共轭函数
觉得构造这部分是难点，也是主要的部分，需要一定的数学功底。下面有大神的推导过程。
第二部分、矩阵快速幂
矩阵快速幂类似于之前学习的整数的快速幂。只是把底数换成了个矩阵。不过对应的有些地方要修改一下。因为要矩阵相乘，我们需要重载一下乘法运算符。

**有个坑就是：因为取模的数字可能是负数，所以取模之前要把前面的数字加上模之后再取模，不然各种WA。**之前学长就提醒过好多次了，不过自己一直没做到这种题（准确来说是做到了不会做，却还没补），结果现在做就WA这里了。

别人家孩子的推导过程

这是链接
https://blog.****.net/u013050857/article/details/44936565

优秀啊

代码

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
typedef long long ll;
using namespace std; 
const ll size=2;//the max size of matrix
ll a,b,n,mod;
struct mat
{
	ll m[size][size];
	mat(){
		memset(m,0,sizeof(m));
	}	
	void init(ll a,ll b,ll c,ll d)
	{
		m[0][0]=a;m[0][1]=b;
		m[1][0]=c;m[1][1]=d;
	}
	mat operator *(const mat &c)//运算符重载 
	{
		mat res;
		for(int i=0;i<size;i++)
			for(int j=0;j<size;j++)
				for(int k=0;k<size;k++)
					res.m[i][j]=(res.m[i][j]+m[i][k]*c.m[k][j]+mod)%mod;//这里已经mod了，外面不用再加 
		return res;	//result
	}
}base;
mat matpow(ll n)//求n次方 
{
	mat ans;
	ans.init(1,0,1,0);//单位矩阵 
	while(n){
		if(n&1) ans=ans*base;//重载运算符里有mod了 
		n>>=1;
		base=base*base;//重载运算符里有mod了
	}
	return ans; 
}
int  main()
{
	//草稿纸上构造好矩阵+矩阵快速幂 	
	while(scanf("%lld %lld %lld %lld",&a,&b,&n,&mod)!=EOF){
		if(n<=1)
			printf("%lld\n",2*a%mod);
		else
		{
			base.init(2*a,-a*a+b,1,0);//推出来的式子,初始化 
			mat ans=matpow(n-1);
			printf("%lld\n",(2*a%mod*ans.m[0][0]+2*ans.m[0][1]+mod)%mod);//矩阵第一个元素即为Cn 
		}
	} 
	return 0;
}