【luogu P1939 【模板】矩阵加速（数列）】题解

题目链接：https://www.luogu.org/problemnew/show/P1939

对于矩阵推序列的式子：

由题意知：

f[x+1] =1f[x] + 0f[x-1] + 1f[x-2]

f[x] = 1f[x] + 0f[x-1] + 0f[x-2]

f[x-1] = 0f[x] + 1f[x-1] + 0*f[x-2]

所以矩阵初项的系数：

1 1 0

0 0 1

1 0 0

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define ll long long

using namespace std;

const int maxn = 110;

const int mod = 1000000007;

struct Matrix{

	ll m[maxn][maxn];

}A, E, Ans;

ll n, q[maxn];

Matrix mul(Matrix A, Matrix B)

{

	Matrix C;

	for(int i = 1; i <= 3; i++)

		for(int j = 1; j <= 3; j++)

		{

			C.m[i][j] = 0;

			for(int k = 1; k <= 3; k++)

				C.m[i][j] = (C.m[i][j] + A.m[i][k] * B.m[k][j] % mod) % mod;

		}

	return C;

}

Matrix qpow(Matrix A, ll k)

{

	Matrix S = E;

	while(k)

	{

		if(k & 1) S = mul(S, A);

		A = mul(A, A);

		k = k >> 1;

	}

	return S;

}

int main()

{

	cin>>n;

    E.m[2][2] = 1;

    E.m[1][1] = 1;

    E.m[3][3] = 1;

    A.m[1][1] = 1;

    A.m[1][2] = 1;

    A.m[2][3] = 1;

    A.m[3][1] = 1;

	for(int i = 1; i <= n; i++)

	{

		ll k;

		cin>>k;

		Ans = qpow(A, k);

		cout<<Ans.m[1][2]<<endl;

	}

	return 0;

}

巴特西

【luogu P1939 【模板】矩阵加速（数列）】题解

最新文章

热门文章

巴特西

【luogu P1939 【模板】矩阵加速（数列）】 题解

最新文章

热门文章

【luogu P1939 【模板】矩阵加速（数列）】题解