个人网站能 做淘客吗/提升关键词

链接

SSL 2513

题目描述

求

的前n项和

样例输入

1

样例输出

1

思路

打表找规律，发现f等价于斐波那契数列
那很显然，题目求斐波那契前n项的和
n很大，所以考虑矩阵乘法
我们构建一个矩阵$ans$

考虑把这个矩阵向$f[i]$转移
显然，$f[i]=(f[i-1]+f[i-2],f[i-1],s[i-2]+f[i-1])$
考虑令它转移的矩阵b

然后就是跑矩阵乘法就可以了

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long longusing namespace std;const ll mo = 1000000007;struct matrix {ll n, m, a[5][5];
}a, b, ans, c;
ll n;matrix operator *(matrix a, matrix b) {c.n = a.n;c.m = b.m;for (ll i = 1; i <= c.n; i++)for (ll j = 1; j <= c.m; j++)c.a[i][j] = 0;for (ll k = 1; k <= a.m; k++)for (ll i = 1; i <= c.n; i++)for (ll j = 1; j <= c.m; j++)c.a[i][j] = (c.a[i][j] + (a.a[i][k] * b.a[k][j]) % mo) % mo;return c;
}void init()
{ans.n = 1, ans.m = 3;ans.a[1][1] = 1;ans.a[1][2] = 1;ans.a[1][3] = 1;b.n = b.m = 3;b.a[1][1] = b.a[1][2] = b.a[1][3] = 1;b.a[2][1] = b.a[3][3] = 1;
}void ksm(int x)
{a = b;x--;while(x){if(x & 1) a = a * b;b = b * b;x /= 2;}
}int main()
{scanf("%d", &n);if(n == 1) {printf("1");return 0;}init();ksm(n - 1);//因为n = 1的时候已经处理过了，所以要减1ans = ans * a;printf("%lld", ans.a[1][3]);
}