当前位置：首页 > news >正文

HDU-5950 Recursive sequence(矩阵乘法)

news 来源：原创 2024/5/5 17:15:34

题意：

给定A、B作为f(1)、f(2)，f(n) = 2*f(n-2) + f(n-1) + n^4，求第n项。

思路：

都会很容易想到矩阵乘法，但是多了一个n^4，所以关键就在于怎么在n^4和(n+1)^4之间进行转移了。

已知：(a+b)^n = C(n, 0)*a^n*b^0 + C(n, 0)*a^(n-1)*b^1 + ... + C(n, i)*a^(n-i)*b^i + ... + C(n, n)*a^0*b^n。

将(n+1)^4展开：n^4 + 4*n^3 + 6*n^2 + 4*n^4 + 1，从而我们就可以构造出矩阵

|(n+1)^4| |1 4 6 4 1| |n^4|
|(n+1)^3| |0 1 3 3 1| |n^3|
|(n+1)^2| = |0 0 1 2 1|*|n^2|
|(n+1)^1| |0 0 0 1 1| |n^1|
| 1 | |0 0 0 0 1| | 1 |

再代入总的矩阵中即可矩阵快速幂求解。

可以发现这题的公式是非线性的，所以利用了展开多项式的方法将非线性部分能够通过线性方法求得。第一次做这种递推题，涨姿势了。

代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 2147493647ll;
struct mtx {
	ll m[7][7];
	mtx(){memset(m, 0, sizeof m);}
};
int t;
ll n, A, B;
mtx multi(mtx x, mtx y)
{
	mtx res;
	for(int k = 0; k < 7; ++k)
	for(int i = 0; i < 7; ++i)
	for(int j = 0; j < 7; ++j)
	res.m[i][j] += x.m[i][k]*y.m[k][j]%mod,
	res.m[i][j] %= mod;
	return res;
}
ll qpow(ll n)
{
	mtx ans, bas, col;
	for(int i = 0; i < 7; ++i) ans.m[i][i] = 1;
	bas.m[0][0] = 1, bas.m[0][1] = 2, bas.m[0][2] = 1,
	bas.m[0][3] = 4, bas.m[0][4] = 6, bas.m[0][5] = 4,
	bas.m[0][6] = 1;
	bas.m[1][0] = 1;
	bas.m[2][2] = 1, bas.m[2][3] = 4, bas.m[2][4] = 6,
	bas.m[2][5] = 4, bas.m[2][6] = 1;
	bas.m[3][3] = 1, bas.m[3][4] = 3, bas.m[3][5] = 3,
	bas.m[3][6] = 1;
	bas.m[4][4] = 1, bas.m[4][5] = 2, bas.m[4][6] = 1;
	bas.m[5][5] = 1, bas.m[5][6] = 1;
	bas.m[6][6] = 1;
	col.m[0][0] = B, col.m[1][0] = A, col.m[2][0] = 2*2*2*2,
	col.m[3][0] = 2*2*2, col.m[4][0] = 2*2, col.m[5][0] = 2,
	col.m[6][0] = 1;
	while(n)
	{
		if(n&1) ans = multi(ans, bas);
		bas = multi(bas, bas);
		n >>= 1;
	}
	ans = multi(ans, col);
	return ans.m[0][0]%mod;
}
int main()
{
	for(scanf("%d", &t); t--;)
	{
		scanf("%lld %lld %lld", &n, &A, &B);
		if(n == 1ll) printf("%lld\n", A);
		else if(n == 2ll) printf("%lld\n", B);
		else printf("%lld\n", qpow(n-2));
	}
	return 0;
}

继续加油~