【矩阵乘法】幼儿园数学题I(ssl 2513)

2024-01-29 23:48

本文主要是介绍【矩阵乘法】幼儿园数学题I(ssl 2513),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

幼儿园数学题I

ssl 2513

题目大意

定义 f n = ( 5 + 1 2 ) n − 1 f_n=\left ( \frac{\sqrt{5}+1}{2}\right )^{n-1} fn=(25 +1)n1,求前n项的和,(对 1 0 9 + 7 10^9+7 109+7取模)(题目貌似出了些问题,实际上 f f f等价于斐波那契数列)

输入样例#1

1

输出样例#1

1

输入样例#2

2

输出样例#2

2

数据范围

1 ⩽ n ⩽ 2 31 − 1 1\leqslant n\leqslant2^{31}-1 1n2311

解题思路

通过打表可以发现 f f f等价于斐波那契数列,那题目就是求斐波那契数列前 n n n项的和
n十分大,不能直接递推
考虑矩阵乘法
设矩阵 [ f i − 2 f i − 1 s i − 2 ] \begin{bmatrix}f_{i-2} & f_{i-1} & s_{i-2}\end{bmatrix} [fi2fi1si2]
在通过乘矩阵 [ 0 1 0 1 1 1 0 0 1 ] \begin{bmatrix}0 & 1 & 0\\ 1 & 1 & 1\\ 0 & 0 & 1\end{bmatrix} 010110011来递推
然后快速幂即可

代码

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define wyc 1000000007
using namespace std;
ll n;
struct matrix
{ll n, m, a[10][10];matrix operator *(const matrix &b) const{matrix c;c.n = n;c.m = b.m;for (int i = 1; i <= c.n; ++i)for (int j = 1; j <= c.m; ++j)c.a[i][j] = 0;for (int i = 1; i <= c.n; ++i)for (int k = 1; k <= m; ++k)for (int j = 1; j <= c.m; ++j)c.a[i][j] = (c.a[i][j] + a[i][k] * b.a[k][j] % wyc) % wyc;return c;}
}A, B;
void Counting(ll x)
{while(x){if (x&1) A = A * B;B = B * B;x>>=1;}
}
int main()
{scanf("%lld", &n);A.n = 1;A.m = B.n = B.m = 3;A.a[1][1] = 1, A.a[1][2] = 1, A.a[1][3] = 1;//初始状态B.a[1][1] = 0, B.a[1][2] = 1, B.a[1][3] = 0;//相乘的矩阵B.a[2][1] = 1, B.a[2][2] = 1, B.a[2][3] = 1;B.a[3][1] = 0, B.a[3][2] = 0, B.a[3][3] = 1;Counting(n - 1);printf("%lld", A.a[1][3]);return 0;
}

这篇关于【矩阵乘法】幼儿园数学题I(ssl 2513)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/658540

相关文章

Python如何获取域名的SSL证书信息和到期时间

《Python如何获取域名的SSL证书信息和到期时间》在当今互联网时代,SSL证书的重要性不言而喻,它不仅为用户提供了安全的连接,还能提高网站的搜索引擎排名,那我们怎么才能通过Python获取域名的S... 目录了解SSL证书的基本概念使用python库来抓取SSL证书信息安装必要的库编写获取SSL证书信息

nginx生成自签名SSL证书配置HTTPS的实现

《nginx生成自签名SSL证书配置HTTPS的实现》本文主要介绍在Nginx中生成自签名SSL证书并配置HTTPS,包括安装Nginx、创建证书、配置证书以及测试访问,具有一定的参考价值,感兴趣的可... 目录一、安装nginx二、创建证书三、配置证书并验证四、测试一、安装nginxnginx必须有"-

python实现简易SSL的项目实践

《python实现简易SSL的项目实践》本文主要介绍了python实现简易SSL的项目实践,包括CA.py、server.py和client.py三个模块,文中通过示例代码介绍的非常详细,对大家的学习... 目录运行环境运行前准备程序实现与流程说明运行截图代码CA.pyclient.pyserver.py参

hdu 4565 推倒公式+矩阵快速幂

题意 求下式的值: Sn=⌈ (a+b√)n⌉%m S_n = \lceil\ (a + \sqrt{b}) ^ n \rceil\% m 其中: 0<a,m<215 0< a, m < 2^{15} 0<b,n<231 0 < b, n < 2^{31} (a−1)2<b<a2 (a-1)^2< b < a^2 解析 令: An=(a+b√)n A_n = (a +

hdu 6198 dfs枚举找规律+矩阵乘法

number number number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description We define a sequence  F : ⋅   F0=0,F1=1 ; ⋅   Fn=Fn

消除安卓SDK更新时的“https://dl-ssl.google.com refused”异常的方法

消除安卓SDK更新时的“https://dl-ssl.google.com refused”异常的方法   消除安卓SDK更新时的“https://dl-ssl.google.com refused”异常的方法 [转载]原地址:http://blog.csdn.net/x605940745/article/details/17911115 消除SDK更新时的“

Android逆向(反调,脱壳,过ssl证书脚本)

文章目录 总结 基础Android基础工具 定位关键代码页面activity定位数据包参数定位堆栈追踪 编写反调脱壳好用的脚本过ssl证书校验抓包反调的脚本打印堆栈bilibili反调的脚本 总结 暑假做了两个月的Android逆向,记录一下自己学到的东西。对于app渗透有了一些思路。 这两个月主要做的是代码分析,对于分析完后的持久化等没有学习。主要是如何反编译源码,如何找到

线性代数|机器学习-P35距离矩阵和普鲁克问题

文章目录 1. 距离矩阵2. 正交普鲁克问题3. 实例说明 1. 距离矩阵 假设有三个点 x 1 , x 2 , x 3 x_1,x_2,x_3 x1​,x2​,x3​,三个点距离如下: ∣ ∣ x 1 − x 2 ∣ ∣ 2 = 1 , ∣ ∣ x 2 − x 3 ∣ ∣ 2 = 1 , ∣ ∣ x 1 − x 3 ∣ ∣ 2 = 6 \begin{equation} ||x

【线性代数】正定矩阵,二次型函数

本文主要介绍正定矩阵,二次型函数,及其相关的解析证明过程和各个过程的可视化几何解释(深蓝色字体)。 非常喜欢清华大学张颢老师说过的一段话:如果你不能用可视化的方式看到事情的结果,那么你就很难对这个事情有认知,认知就是直觉,解析的东西可以让你理解,但未必能让你形成直觉,因为他太反直觉了。 正定矩阵 定义 给定一个大小为 n×n 的实对称矩阵 A ,若对于任意长度为 n 的非零向量 ,有 恒成

在幼儿园管理系统中,会议管理申请会议修改模块:多个与会人员的回显和修改(编辑)!

在幼儿园管理系统中,会议管理>申请会议>修改模块:多个与会人员的回显(复选框)和修改(编辑)!在处理与会人员的回显(复选框)和修改(编辑)出点问题。无法正确的回显(复选框)出来与会人员和修改(编辑)。 最后终于解决:修改(编辑)的思路是:先把原来的该会议记录下的所有与会人员删除,在添加,即可实现修改(编辑)功能。回显(复选框)的思路是:设置一个flag,判断一下是否要选中(复选框),即可实现