初始矩阵 $A$：

转移矩阵 $B$：

答案就在 $A \times B^{n-1} 的右上角$。

但是这样写只有 70pts，龟速乘、取模什么的都注意到了，求各位大佬帮忙看看哪里出了问题。

#include<bits/stdc++.h>
#define int long long
#define N 105
using namespace std;

int mod,k,b,x0,x1,n,g;

int qmul(int a,int b)
{
	int ret = 0;
	while(b)
	{
		if(b&1)ret = (ret + a)%mod;
		b >>= 1;
		a = a*2%mod;
	}
	return ret;
}

struct mat
{
	int v[4][4];
	mat(){memset(v,0,sizeof v);}
	void init()
	{
		for(int i = 1;i <= 3;i++)
			v[i][i] = 1;
	}
};
mat operator * (mat a,mat b)
{
	mat ret;
	for(int i = 1;i <= 3;i++)
		for(int j = 1;j <= 3;j++)
			for(int k = 1;k <= 3;k++)	
				(ret.v[i][j] += qmul(a.v[i][k],b.v[k][j])) %= mod;
	return ret;
}
mat operator ^ (mat a,int b)
{
	mat ret;ret.init();
	while(b)
	{
		if(b&1)ret = ret * a;
		b >>= 1;
		a = a * a;
	}
	return ret;
}

signed main()
{
	scanf("%lld%lld%lld%lld%lld%lld",&mod,&k,&b,&x0,&n,&g);
	x1 = (k*x0+b) % mod;
	if(n == 0)return printf("%lld\n",x0%g),0;
	if(n == 1)return printf("%lld\n",x1%g),0; 
	mat a,base,ans;
	a.v[1][1] = x0,a.v[1][2] = 1,a.v[1][3] = x1;
	base.v[2][2] = base.v[3][1] = 1;
	base.v[2][3] = b,base.v[3][3] = k;
	ans = a*(base^(n-1));
	printf("%lld\n",ans.v[1][3]%g);
	return 0;
}