【Loj10222】佳佳的Fibonacci

题面

题解

可以发现\(T(n)\)无法用递推式表示。

于是我们做如下变形：

\[T(n) = \sum _ {i = 1} ^ n i \times f_i \\
S(n) = \sum _ {i = 1} ^ n f_i \\
\therefore nS(n) - T(n) = \sum _ {i = 1} ^ {n - 1} (n - i)f_i \\
\]

令\(p(n) = nS(n) - T(n)\)

则\(p(n + 1) = p(n) + S(n)\)

用矩阵乘法即可。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define RG register

#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);

inline int read()

{

	int data = 0, w = 1;

	char ch = getchar();

	while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();

	if(ch == '-') w = -1, ch = getchar();

	while(ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();

	return data * w;

}

int n, Mod;

inline void Add(int &x, const int &y) { x += y; if(x >= Mod) x -= Mod; }

inline int Mul(const int &x, const int &y) { return 1ll * x * y % Mod; }

template<int N, int M>

struct Matrix

{

	int a[4][4];

	Matrix() { memset(a, 0, sizeof(a)); }

	inline int *operator [] (const int &id) { return a[id]; }

	template<int K> inline Matrix<N, K> operator * (const Matrix<M, K> &b) const

	{

		Matrix<N, K> c;

		for(RG int i = 0; i < N; i++)

			for(RG int j = 0; j < M; j++)

				for(RG int k = 0; k < K; k++)

					Add(c[i][k], 1ll * a[i][j] * b.a[j][k] % Mod);

		return c;

	}

};

Matrix<1, 4> S;

Matrix<4, 4> T;

int main()

{

	n = read(); Mod = read();

	int Tmp = n;

	S[0][1] = T[0][0] = T[0][1] = T[0][2] = T[1][0] = T[1][2] = T[2][2] = T[2][3] = T[3][3] = 1;

	while(Tmp)

	{

		if(Tmp & 1) S = S * T;

		T = T * T, Tmp >>= 1;

	}

	printf("%d\n", (Mul(n, S[0][2]) - S[0][3] + Mod) % Mod);

	return 0;

}

巴特西

【Loj10222】佳佳的Fibonacci

题面

题解

最新文章

热门文章