Fibonacci数列(codevs 1250)
2024-08-31 04:05:56
题目描述 Description
定义:f0=f1=1, fn=fn-1+fn-2(n>=2)。{fi}称为Fibonacci数列。
输入n,求fn mod q。其中1<=q<=30000。
输入描述 Input Description
第一行一个数T(1<=T<=10000)。
以下T行,每行两个数,n,q(n<=109, 1<=q<=30000)
输出描述 Output Description
文件包含T行,每行对应一个答案。
样例输入 Sample Input
3
6 2
7 3
7 11
样例输出 Sample Output
1
0
10
数据范围及提示 Data Size & Hint
1<=T<=10000
n<=109, 1<=q<=30000
/*
矩阵乘法求斐波那契数列
*/
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
ll a[][],b[][],c[][],ans[][],n,mod;
void work()
{
b[][]=ans[][]=;
b[][]=ans[][]=;
b[][]=ans[][]=;
b[][]=ans[][]=;
while(n)
{
if(n&)
{
for(int k=;k<=;k++)
for(int i=;i<=;i++)
for(int j=;j<=;j++)
c[i][j]=(c[i][j]+(ans[i][k]*b[k][j]%mod)%mod);
for(int i=;i<=;i++)
for(int j=;j<=;j++)
ans[i][j]=c[i][j],c[i][j]=;
}
for(int k=;k<=;k++)
for(int i=;i<=;i++)
for(int j=;j<=;j++)
c[i][j]=(c[i][j]+(b[i][k]*b[k][j]%mod)%mod);
for(int i=;i<=;i++)
for(int j=;j<=;j++)
b[i][j]=c[i][j],c[i][j]=;
n/=;
}
printf("%lld\n",(ans[][]+ans[][])%mod);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
cin>>n>>mod;
if(n<=)printf("%lld\n",n);
else n--,work();
}
return ;
}
最新文章
- #ThinkPHP_3.2.2模型# where查询条件汇总
- XMPP iOS客户端实现一:服务器
- 日常contest总结
- Android Programming: Pushing the Limits -- Chapter 1: Fine-Tuning Your Development Environment
- 对Object类中方法的深入理解
- SSD在SQLServer中的应用
- 使用C#三维图形控件进行曲线曲面分析
- JasperReports+iReport在eclipse中的使用
- JS省队集训记
- XML格式以及相关libxml库学习
- OpenCV(7)-图像直方图
- Construct Binary Tree From Inorder and Preorder/Postorder Traversal
- C#入门经典(2-重置窗体布局,界面介绍,错误列表)
- gtk+3.0的环境配置及基于gtk+3.0的python简单样例
- mysql数据库内容相关操作
- Jmeter安装使用
- vux的x-input的源码分析
- 学了近一个月的java web 感想
- 【转】Mysql学习---MySQL悲观锁中的排它锁
- 向 webview 添加 userScript
热门文章
- jQuery Validate插件实现表单强大的验证功能
- 解决input输入框在iOS中有阴影问题
- Sublime Text Version 3.0,Build3143注册码
- Linux下MySql数据的导入导出
- HTML--使用提交按钮,提交数据
- action=";post"; 、 servletconfig 、 servletcontext 、getPrintWiter() 、context-param、 init-param(第一个完整的servlet)
- day01_12/11/2016_Spring入门PPT
- 【LeetCode】467. Unique Substrings in Wraparound String
- Git系列学习(1)-Git安装
- CentOS7阿里云服务器,python程序requests无法正常post网站(报502)