矩阵快速幂

#include <bits/stdc++.h>
using namespace std;
long long n,k,mod;
struct Matrix {
	long long a[3][3];
	Matrix operator * (const Matrix &x) {
		Matrix ans;
		for(int i = 1;i <= 2;i ++) {
			for(int j = 1;j <= 2;j ++) {
				for(int k = 1;k <= 2;k ++) {
					ans.a[i][j] = (ans.a[i][j] + a[i][k] * x.a[k][j]) % mod;
				}
			}
		}
    	return ans;
	}
}ans,base;
void ksm(long long x) {
	while(x) {
		if(x & 1) {
			ans = ans * base;
		}
		base = base * base;
		x >>= 1;
	}
}
int main() {
	scanf("%lld%lld%lld",&mod,&k,&n);
	if(n == 0) {
		printf("2");
		return 0;
	}
	if(n == 1) {
  		printf("%lld",k % mod);
  		return 0;
	}
	base.a[1][1] = k;
	base.a[1][2] = 1;
	base.a[2][1] = -1;
	ans.a[1][1] = (k * k - 2) % mod;
	ans.a[1][2] = k % mod;
	ksm(n - 2);
  	printf("%lld",(ans.a[1][1] + mod) % mod);
  	return 0;
}

，第三个样例死活过不去，感觉和题解一模一样，不知道哪里错了。