为啥两个MLE?Orz
查看原帖
为啥两个MLE?Orz
339978
大白菜ac楼主2020/5/26 00:23
#include <iostream>
using namespace std;
typedef long long ll;
const ll M = 1e9 + 7;

struct node {//定义结构体用来表示一个矩阵
	ll m[3][3];
};

node Multiply(node x, node y, int r) {//矩阵乘法,r表示矩阵的阶数
	node t;
	for (int i = 1; i <= r; i++) 
		for (int j = 1; j <= r; j++) {
			t.m[i][j] = 0;
			for (int k = 1; k <= r; k++) {
				t.m[i][j] += (x.m[i][k] * y.m[k][j]);//关键
			}
			t.m[i][j] = t.m[i][j] % M;
		}
	return t;
}

node Dsz(ll x, node a) {//矩阵快速幂,求矩阵a的x次方
	if (x == 1)
		return a;
	if (x == 2)
		return Multiply(a, a, 2);
	if (x % 2) {
		node t = Dsz(x / 2, a);
		node r = Multiply(t, t, 2);
		return Multiply(r, a, 2);
	}
	else {
		node t = Dsz(x / 2, a);
		return Multiply(t, t, 2);
	}
}

int main() {
	ll n;
	cin >> n;
	n -= 2;
	node a, b;
	a.m[1][1] = 0, a.m[1][2] = 1, a.m[2][1] = 1, a.m[2][2] = 1;//初始化矩阵
	b.m[1][1] = 1, b.m[2][1] = 1;//压根没用上
	node s = Dsz(n, a);
	cout << (s.m[2][1] + s.m[2][2]) % M;
	return 0;
}
2020/5/26 00:23
加载中...