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取余
介绍两种矩阵构造方法:
方法一:
设
构造一个一个矩阵维护
代码:
/**/
#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;
}
/**/
方法二:
设
则有
其中
所以我们维护
知道了所有的
代码：
/**/
#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函数即也是线性的)
京公网安备 11010502036488号