斐波那契求和(矩阵快速幂+多项式拆分)

https://ac.nowcoder.com/acm/contest/5477/J

Fib(i)表示斐波那契函数，Fib(n)=Fib(n-1)+Fib(n-2)，如Fib(1)=1，Fib(2)=1，Fib(3)=2，Fib(4)=3，Fib(5)=5，Fib(6)=8。

给定正整数n和k，求：

由于结果太大，你需要把求和的结果对998244353取余

介绍两种矩阵构造方法:

方法一:

设，那么

构造一个一个矩阵维护一共2(k+1)+1项

代码:

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

const long long mod = 998244353;

int k, M;
LL n, c[105][105], a[205][205], p[105];

void init(int k){
	c[0][0] = 1;
	for (int i = 1; i <= k; i++){
		c[i][0] = 1;
		for (int j = 1; j <= i; j++){
			c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
		}
	}
	p[0] = 1;
	for (int i = 1; i <= k; i++) p[i] = (p[i - 1] << 1) % mod;
}

LL poww(LL x, LL num){
	LL res = 1;
	while(num){
		if(num & 1) res = res * x % mod;
		x = x * x % mod;
		num >>= 1;
	}
	return res;
}

void mul(LL a[205][205], LL b[205][205]){
	LL c[M + 1][M + 1];
	memset(c, 0, sizeof(c));
	for (int i = 0; i <= M; i++){
		for (int j = 0; j <= M; j++){
			if(a[i][j] == 0) continue;
			for (int k = 0; k <= M; k++){
				c[i][k] = (c[i][k] + a[i][j] * b[j][k] % mod) % mod;
			}
		}
	}
	for (int i = 0; i <= M; i++){
		for (int j = 0; j <= M; j++){
			a[i][j] = c[i][j];
		}
	}
}

LL solve(LL num){
	if(num == 1) return 1;
	if(num == 2) return (p[k] + 1) % mod;
	num -= 2;
	a[0][0] = 1;
	for (int i = 1; i <= k + 1; i++) a[0][i] = c[k][i - 1], a[0][i + k + 1] = c[k][i - 1];
	for (int i = 1; i <= k + 1; i++){
		for (int j = i; j <= k + 1; j++){
			a[i][j] = c[k - i + 1][j - i];
			a[i][j + k + 1] = c[k - i + 1][j - i];
		}
	}
	for (int i = k + 2; i <= M; i++){
		for (int j = 1; j <= k + 1; j++){
			a[i][j + i - k - 2] = c[k - i + k + 2][j - 1];
		}
	}
	// for (int i = 0; i <= M; i++){
	// 	for (int j = 0; j <= M; j++){
	// 		printf("%lld ", a[i][j]);
	// 	}
	// 	printf("\n");
	// }
	LL res[205][205];
	for (int i = 0; i <= M; i++){
		for (int j = 0; j <= M; j++){
			if(i == j) res[i][j] = 1;
			else res[i][j] = 0;
		}
	}
	while(num){
		if(num & 1) mul(res, a);
		mul(a, a);
		num >>= 1;
	}
	LL ans = (p[k] + 1) * res[0][0] % mod;
	for (int i = 1; i <= k + 1; i++) ans = (ans + p[k + 1 - i] * res[0][i] % mod) % mod;
	for (int i = 1; i <= k + 1; i++) ans = (ans + p[k + 1 - i] * res[0][i + k + 1] % mod) % mod;
	return ans;
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%lld %d", &n, &k);
	init(k);
	M = (k + 1) * 2;
	printf("%lld\n", solve(n));

	return 0;
}
/**/

方法二:

设

则有

$= \sum_{k-1}^{i=0}\binom{k}{i}G_{i}(n)$

其中

所以我们维护共k+3个变量

知道了所有的后，知道，然后通过循环依次求得,最终得出

代码：

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

const long long mod = 998244353;

int k, M;
LL n, c[105][105], a[105][105], p[105], fj[105], F[105];

void init(){
	c[0][0] = 1;
	for (int i = 0; i <= k; i++){
		c[i][0] = 1;
		for (int j = 1; j <= i; j++){
			c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
		}
	}
	p[0] = 1;
	for (int i = 1; i <= k; i++) p[i] = n % mod * p[i - 1] % mod;
}

void mul(LL a[105][105], LL b[105][105]){
	LL c[M + 1][M + 1];
	memset(c, 0, sizeof(c));
	for (int i = 0; i <= M; i++){
		for (int j = 0; j <= M; j++){
			for (int k = 0; k <= M; k++){
				c[i][j] = (c[i][j] + a[i][k] * b[k][j] % mod) % mod;
			}
		}
	}
	for (int i = 0; i <= M; i++){
		for (int j = 0; j <= M; j++){
			a[i][j] = c[i][j];
		}
	}
}

LL solve(LL num){
	if(num == 1) return 1;
	for (int i = 0; i < k; i++){
		for (int j = i; j <= k; j++){
			a[i][j] = c[k - i][k - j];
		}
	}
	a[k][k] = a[k][k + 1] = a[k][k + 2] = 1;
	a[k + 1][k + 1] = a[k + 1][k + 2] = a[k + 2][k + 1] = 1;
	LL res[105][105];
	for (int i = 0; i <= M; i++){
		for (int j = 0; j <= M; j++){
			if(i == j) res[i][j] = 1;
			else res[i][j] = 0;
		}
	}
	
	while(num){
		if(num & 1) mul(res, a);
		mul(a, a);
		num >>= 1;
	}
	for (int i = 0; i <= k; i++){
		fj[k - i] = res[i][k + 2];
		// printf("fj = %d %lld\n", i, fj[k - i]);
	}
	for (int i = 0; i <= k; i++){
		LL sum = fj[i];
		for (int j = 0; j < i; j++){
			if(j & 1) sum = (sum + p[i - j] * F[j] % mod * c[i][j] % mod);
			else sum = (sum - p[i - j] * F[j] % mod * c[i][j] % mod);
		}

		if(i & 1) F[i] = -sum;
		else F[i] = sum;
	}
	return (F[k] % mod + mod) % mod;
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%lld %d", &n, &k);
	M = k + 2;
	init();
	printf("%lld\n", solve(n));

	return 0;
}
/**/

方法三：BM板子，首先列出前1000项放入BM板子，然后直接跑就行了，这里代码也不放了。满足线性关系(G函数线性的，F函数即也是线性的)