本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-05-16 21:57:22

前言：

当年的国赛题目现在居然变成了一个绿题
本题解只是我的做题思路，还没实际写代码测试，可能有错。

题目分析：

题目给定的是一个递推式，序列里一个数由上一个数生成。而且数据范围特别大，要求第 $10^{18}$ 项，不难想到通过矩阵加速来解决这道题。
设两个矩阵：
$ B = \left[ {\begin{array}{cc} x_{0}\ c\ \end{array} } \right] $

$ C = \left[ {\begin{array} {cc} x_{1}\ c\ \end{array} } \right] $

现在要构造出一个矩阵 $B$，使得 $A \cdot B = C$
因为 $x_1 = x_{0} \cdot a + c \cdot 1$，所以矩阵 $A$ 的第一行为：$[a,1]$。
因为 $c = x_0 \cdot 0 + c \cdot 1$，所以矩阵 $A$ 的第二行为 $[0,1]$
也就是说：
$ A = \left[ {\begin{array} {cc} a,1\ 0,1\ \end{array} } \right] $

现在构造出了矩阵，那么非常的显然，答案就是：$A^{n} \cdot B$，矩阵快速幂即可。 算了我对“显然”解释一下：第 $n$ 项是由第 $n-1$ 项 乘矩阵 $A$ 得来的，不能理解手动推算一下就能的出来。

代码：

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	typedef long long ll;
	ll n,m,a,c,x0,g;
	struct Matrix
	{
		ll imap[2][2];
		Matrix()
		{
			memset(imap,0,sizeof(imap));
		}
		void init()
		{
			imap[0][0]=imap[1][1]=1;
		}
		ll guisucheng(ll a,ll b)
		{
			ll res=0;
			while(b)
			{
				if(b&1)res=(res+a)%m;
				a=a*2%m;
				b>>=1;
			}
			return res;
		}
		Matrix operator*(Matrix b)
		{
			Matrix res;
			for(int i=0;i<2;i++)
			{
				for(int j=0;j<2;j++)
				{
					for(int k=0;k<2;k++)
					{
						res.imap[i][j]+=guisucheng(imap[i][k],b.imap[k][j]);
						res.imap[i][j]%=m;
					}
				}
			}
			return res;
		}
	};
	Matrix ksm(Matrix base,ll b)
	{
		Matrix res;
		res.init();
		while(b)
		{
			if(b&1)res=res*base;
			base=base*base;
			b>>=1;
		}
		return res;
	}
	Matrix A,B;
	void main()
	{
		scanf("%lld%lld%lld%lld%lld%lld",&m,&a,&c,&x0,&n,&g);
		A.imap[0][0]=a;
		A.imap[0][1]=A.imap[1][1]=1;
		B.imap[0][0]=x0;
		B.imap[1][0]=c;
		Matrix ans=ksm(A,n)*B;
		printf("%lld",ans.imap[0][0]%g);
	}
}
int main()
{
	Main::main();
	return 0;
}