斐波那契和（“科大讯飞杯”第十七届同济大学程序设计预选赛暨高校网络友谊赛 J，矩阵快速幂）

同济大学程序设计预选赛暨高校网络友谊赛 J，矩阵快速幂）"/>

斐波那契和（“科大讯飞杯”第十七届同济大学程序设计预选赛暨高校网络友谊赛 J，矩阵快速幂）

一.题目链接：

斐波那契和

二.题目大意：

求  

三.分析：

比赛时套杜教 BM 一直wa，赛后才发现模数写错...(太蠢了

由于杜教 BM 直接套上模板改改模数就能 AC，这里只给出非杜教 BM 解法(杜教 BM 他不香吗？

首先做一下符号解释

 符号化后，题目即求 

然后求  的递推式

当计算  时，前面  的值均已计算完毕，因此我们只需求 

下面求  的递推式

当  时

当  时

至此我们即可用矩阵快速幂求解 

具体来讲

可知 

递归计算可知 

四.代码实现：

#include <bits/stdc++.h>
using namespace std;typedef long long ll;const int M = (int)1e2 + 4;
const ll mod = (ll)998244353;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;ll n; int k;
ll g[M + 5];
ll f[M + 5];struct node
{ll D[M + 5][M + 5];
};ll quick(ll a, ll b)
{ll sum = 1;while(b){if(b & 1) sum = sum * a % mod;a = a * a % mod;b >>= 1;}return (sum + mod) % mod;
}node mul(node a, node b)
{node c; memset(c.D, 0, sizeof(c.D));for(int i = 0; i < M; ++i)for(int j = 0; j < M; ++j)for(int l = 0; l < M; ++l)c.D[i][j] = (c.D[i][j] + a.D[i][l] * b.D[l][j] % mod) % mod;return c;
}node quick(node a, ll b)
{node sum; memset(sum.D, 0, sizeof(sum.D));for(int i = 0; i < M; ++i) sum.D[i][i] = 1;while(b){if(b & 1) sum = mul(sum, a);a = mul(a, a);b >>= 1;}return sum;
}int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);scanf("%lld %d", &n, &k);node A, B;memset(A.D, 0, sizeof(A.D));memset(B.D, 0, sizeof(B.D));A.D[0][k] = 1, A.D[0][k + 1] = 2, A.D[0][k + 2] = 1, A.D[0][k + 3] = 1;for(int j = k; j >= 0; --j){B.D[k][j] = 1;for(int i = k - 1; i >= j; --i) B.D[i][j] = (B.D[i][j + 1] + B.D[i + 1][j + 1]) % mod;}B.D[k][k] = 0;B.D[k + 1][k] = B.D[k + 1][k + 1] = B.D[k + 1][k + 2] = 1;B.D[k + 2][k] = B.D[k + 2][k + 1] = 1;B.D[k + 3][k] = -1, B.D[k + 3][k + 3] = 1;node G = mul(A, quick(B, n - 1));for(int i = 0; i <= k; ++i) g[i] = G.D[0][k - i];f[0] = G.D[0][k + 1] - 1;for(int i = 1; i <= k; ++i){f[i] = g[i];for(int j = 0; j <= i - 1; ++j) f[i] = (f[i] + (((j&1)<<1)-1) * B.D[k - j][k - i] * quick(n % mod, i - j) % mod * f[j] % mod) % mod;if(i & 1) f[i] *= -1;f[i] = (f[i] + mod) % mod;}printf("%lld\n", f[k]);return 0;
}