愿风裁尽尘中沙 与君咫尺共天涯 弱而不改凌云誓 穷且不坠青云志

https://ac.nowcoder.com/acm/contest/885/B

题意：给x0 x1 a b n mod xn=a*xn-1+b*xn-2
最后结果取模 n可能很大很大 需要改成10进制的快速幂 要不不好处理那个很长很长的n

#include <set>
#include<iostream>
#include <cstdio>
#include <algorithm>
#include<string>
#include<cstring>
using namespace std;
const int maxn = 2;

typedef long long ll;

int mod;

struct mat {
	int m[maxn][maxn];
	mat() {//构造函数为构造单位矩阵
		m[0][0] = m[1][1] = 1;
		m[0][1] = m[1][0] = 0;
	}
}unit;

mat operator *(mat a, mat b) {
	mat ret;//矩阵乘法运算
	ll x;
	for (int i = 0; i < maxn; i++) {
		for (int j = 0; j < maxn; j++) {
			x = 0;
			for (int k = 0; k < maxn; k++) {
				x += ((ll)a.m[i][k] * b.m[k][j]) % mod;
			}
			ret.m[i][j] = x % mod;
		}
	}
	return ret;
}

mat pow_mat(mat a, int n) {//常规快速幂
	mat ret = unit;
	while (n) {
		if (n & 1) {
			ret = ret * a;
		}
		a = a * a;
		n >>= 1;
	}
	return ret;
}

mat pow_mat(mat a, char s[]) {//十进制快速幂
	mat res;
	for (int i = strlen(s + 1); i >= 1; i--) {//相当于x>>=1;
		if (s[i] != '0')//与二进制同理 如果这一位是0的话 就跳过
		{
			res = res * pow_mat(a, s[i] - '0');//否则计算
		}
		a = pow_mat(a, 10);//相当于a=a*a;
	}
	return res;
}

char s[1000011];

int main() {
	int x0, x1, A, B;
	scanf("%d%d%d%d", &x0, &x1, &A, &B);
	scanf("%s%d", s + 1, &mod);
	x0 %= mod;
	x1 %= mod;
	A %= mod;
	B %= mod;
	if (strlen(s + 1) == 1 && s[1] == '1') {//一次方的情况
		printf("%d\n", x1);
		return 0;
	}
	mat a;
	a.m[0][0] = x1;
	a.m[0][1] = x0;
	mat b;
	b.m[0][0] = A;
	b.m[0][1] = 1;
	b.m[1][0] = B;
	b.m[1][1] = 0;
	//mat c = a * b;
	//cout << c.m[0][0];
	mat c = pow_mat(b, s);
	mat d = a * c;
	cout << d.m[0][1] % mod << endl;//这个地方卡了一会 因为字符串我不会处理-1这种情况 最后突然明白 x0是n项 x1是n-1项
	return 0;
}

#include <set>
#include<iostream>
#include <cstdio>
#include <algorithm>
#include<string>
#include<cstring>
using namespace std;
const int maxn = 2;

typedef long long ll;

int mod;

struct mat {
	int m[maxn][maxn];
	mat() {//构造函数为构造单位矩阵
		m[0][0] = m[1][1] = 1;
		m[0][1] = m[1][0] = 0;
	}
}unit;

mat operator *(mat a, mat b) {
	mat ret;//矩阵乘法运算
	ll x;
	for (int i = 0; i < maxn; i++) {
		for (int j = 0; j < maxn; j++) {
			x = 0;
			for (int k = 0; k < maxn; k++) {
				x += ((ll)a.m[i][k] * b.m[k][j]) % mod;
			}
			ret.m[i][j] = x % mod;
		}
	}
	return ret;
}

mat pow_mat(mat a, int n) {//常规快速幂
	mat ret = unit;
	while (n) {
		if (n & 1) {
			ret = ret * a;
		}
		a = a * a;
		n >>= 1;
	}
	return ret;
}

mat pow_mat(mat a, char s[]) {//十进制快速幂
	mat res;
	for (int i = strlen(s + 1); i >= 1; i--) {//相当于x>>=1;
		if (s[i] != '0')//与二进制同理 如果这一位是0的话 就跳过
		{
			res = res * pow_mat(a, s[i] - '0');//否则计算
		}
		a = pow_mat(a, 10);//相当于a=a*a;
	}
	return res;
}

char s[1000011];

int main() {
	int x0, x1, A, B;
	scanf("%d%d%d%d", &x0, &x1, &A, &B);
	scanf("%s%d", s + 1, &mod);
	x0 %= mod;
	x1 %= mod;
	A %= mod;
	B %= mod;
	if (strlen(s + 1) == 1 && s[1] == '1') {//一次方的情况
		printf("%d\n", x1);
		return 0;
	}
	mat a;
	a.m[0][0] = x1;
	a.m[0][1] = x0;
	mat b;
	b.m[0][0] = A;
	b.m[0][1] = 1;
	b.m[1][0] = B;
	b.m[1][1] = 0;
	//mat c = a * b;
	//cout << c.m[0][0];
	mat c = pow_mat(b, s);
	mat d = a * c;
	cout << d.m[0][1] % mod << endl;//这个地方卡了一会 因为字符串我不会处理-1这种情况 最后突然明白 x0是n项 x1是n-1项
	return 0;
}