#O1052. 斐波那契第 n 项
斐波那契第 n 项
题目描述
定义 ,,,求 。
题目类型
矩阵快速幂
输入格式
一行一个整数 。
输出格式
一行一个整数,表示 。
样例 #1
样例输入 #1
10
样例输出 #1
55
数据规模与约定
| 数据范围 | 说明 |
|---|---|
| 项数 |
- 用 矩阵快速幂,所有乘法取模,注意
unsigned long long读入。
定义 F1=1,F2=1,Fn=Fn−1+Fn−2,求 Fnmod(109+7)。
矩阵快速幂
一行一个整数 n。
一行一个整数,表示 Fnmod(109+7)。
10
55
| 数据范围 | 说明 |
|---|---|
| 1≤n≤1018 | 项数 |
unsigned long long 读入。