记录编号	577254	评测结果	AAAAAAAAAA
题目名称	[AHOI 2004] 数字迷阵	最终得分	100
用户昵称	HeSn	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2022-10-29 07:10:52	内存使用	0.00 MiB

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1000010;
int n, m, p, a[MAXN], b[MAXN], cnt;
struct node {
	int g[3][3];
}e, f;
node mul(node x, node y) {
	node z;
	for(int i = 1; i < 3; i ++) {
		for(int j = 1; j < 3; j ++) {
			z.g[i][j] = 0;
		}
	}
	for(int i = 1; i < 3; i ++) {
		for(int j = 1; j < 3; j ++) {
			for(int k = 1; k < 3; k ++) {
				z.g[i][j] += x.g[i][k] * y.g[k][j];
				z.g[i][j] %= p;
			}
		}
	}
	return z;
}
signed main() {
	freopen("nummaze.in", "r", stdin);
	freopen("nummaze.out", "w", stdout);
	cin >> n >> m >> p;
	a[1] = 1;
	a[2] = 2;
	for(int i = 3; i; i ++) {
		a[i] = a[i - 1] + a[i - 2];
		cnt = i;
		if(a[i] * 2 >= n) {
			break;
		}
	}
	b[1] = 3;
	b[2] = 5;
	for(int i = 3; i <= cnt; i ++) {
		b[i] = b[i - 1] + b[i - 2];
	}
	int x = 1, w = n - 1;
	for(int i = cnt; i >= 1; i --) {
		while(w >= a[i]) {
			w -= a[i];
			x += b[i];
		}
	}
	m --;
	e.g[1][1] = e.g[2][2] = 1;
	f.g[1][1] = f.g[1][2] = f.g[2][1] = 1;
	while(m) {
		if(m % 2 == 1) {
			e = mul(e, f);
		}
		m /= 2;
		f = mul(f, f);
	}
	cout << (x * e.g[2][2] + (x * 2 - (n - 1)) * e.g[2][1]) % p;
	return 0;
}