学步园

/*
由f(n)=f(n-1)+f(n-2)构造矩阵
令
Fn(1,2) = |f(n) f(n-1)|
A(2 2) = |1 1|
		 |1 0|
F1(1 2) = |1 0|
Fn = F(n-1) * A = F1 * A ^ (n-1)
代入n = g(i) = k * i + b 得：Fn = F1 * A ^ (k * i + b - 1)
1)b > 1
Fn = F1 * A^(b-1) * (A^k)^i
Sum(Fn) = F1 * A^(b-1) * Sum((A^k)^i)
2)b = 1
Fn = F1 * (A^k)^i
Sum(Fn) = F1 * Sum((A^k)^i)
3)b = 0
Fn = F1 * A^(k-1) * (A^k)^i------------------n = n - 1
Sum(Fn) = F1 * A^(k-1) * Sum((A^k)^i)--------n = n - 1
其中Sum((A^k)^i)用solve进行二分求和
*/
#include "Mat.h"
#include <iostream>
using namespace std;

int main()
{
	Mat A(2, 2), F1(1, 2), e(2, 2), ans(1, 2), temp(2, 2);
	int b, n, k;
	while(cin>>k>>b>>n>>mod)
	{
		//全1矩阵
		A.clear(2);A.s[1][1] = 0;
		F1.clear(1);
		e.clear(1);
		ans.clear();

		temp = A;
		if(b > 1)
		{
			temp.Er_work(b-1);
			F1.Multiply(temp);
		}
		else if(b == 0)
		{
			n--;
			temp.Er_work(k-1);
			F1.Multiply(temp);
		}
		A.Er_work(k);
		A.solve(n-1);
		A.Add(e);
		F1.Multiply(A);
		printf("%I64d\n",F1.s[0][0]);
	}
	return 0;
}