本文共 984 字，大约阅读时间需要 3 分钟。

大家都知道 Fibonacci 数列吧，f1=1,f2=1,f3=2,f4=3,…,fn=fn−1+fn−2。

现在问题很简单，输入 n 和 m，求 fn 的前 n 项和 Snmodm。

输入格式

输出格式

数据范围

这道题我本来想用简单的暴力解决问题，但是我发现测试样例很大，我知道暴力肯定过不去，然后看y总的视频，才了解到一个交线性代数的矩阵相乘算法，我现在还在大一，我们还没开始线性代数的学习，所以我理解起来会有点很吃力，然后我就看b站的视频，但是毫无效果，然后我就对y总的代码进行了模拟，才知道了矩阵相乘的规律。

其实y总的推理古城也很复杂，这道题注定不会很简单的去解决。

所以最主要的思想是：

因为最后的结果是矩阵

然后我们的代码应该是

最后的代码如下：

#include
   
    #include
    
     #include
     
      using namespace std;typedef long long LL;const int N=3;int n,mod;int a[N][N]={       {   0,1,0},    {   1,1,1},    {   0,0,1}};int fi[N]={   1,1,1};void mul(int t[],int b[],int c[][N]){       int temp[N]={   0};    for(int i=0;i
      
       >n>>mod;    n--;    while(n)    {           if(n&1) mul(fi,fi,a);        mul(a,a,a);        n>>=1;    }    cout<