/* * [题意] * F(0) = 0; F(1) = 1; F(n) = F(n-1)+F(n-2); (斐波那契数列) * 设C[i][j]为组合数i种元素中取j种元素的方法 * 给出n、m,求( C[n][0]*F(0)+C[n][1]*F(1)+...+C[n][k]*F(k) ) % m; * [解题方法] * 设矩阵 A = |1 1| * |1 0| * 设矩阵 B = (A^n) * 则B[0][0] = F(n-1); B[0][1] = B[1][0] = F(n); B[1][1] = F(n-1); * { 注:上述为斐波那契矩阵的性质 } * 令D = ( C[n][0]*(A^0) + C[n][1]*(A^1) +...+ C[n][k]*(A^k) ) % m * = ( (A + E)^n ) % m (E为单位阵) * { 类比二次多项式(x+1)^n = C[n][0]+C[n][0]*x+...+C[n][k]*(x^k) } * 则D[1][0]或D[0][1]即为所求 */ #include <iostream> #include <cstdio> #include <cstring> using namespace std; #define M 2 #define LL long long #define FF(i, n) for(int i = 0; i < n; i++) int ret[M][M], mod; int init[M][M]; int ss[M][M] = {2, 1, 1, 1}; void ini(int n) { FF(i, n) FF(j, n) init[i][j] = ss[i][j]; } void matmul(int a[][M], int b[][M], int n) { int tp[M][M] = {0}; FF(i, n) FF(k, n) if(a[i][k]) FF(j, n) if(b[k][j]) tp[i][j] = (tp[i][j] + (LL)a[i][k]*b[k][j]) % mod; FF(i, n) FF(j, n) a[i][j] = tp[i][j]; } void qmod(int n, int b) { FF(i, n) FF(j, n) ret[i][j] = (i==j); for( ; b; b >>= 1) { if (b & 1) matmul(ret, init, n); matmul(init, init, n); } } int main() { int t, n; scanf("%d", &t); while (t--) { scanf("%d%d", &n, &mod); ini(M); qmod(M, n); printf("%d\n", ret[0][1]); } return 0; }
相关推荐
T型三电平+SVPWM的下垂控制与双闭环中点电位平衡控制.pdf
STM32真实企业级项目:锅炉控制器源码、原理图与PCB图.pdf
STM32F103 Modbus主站源码:正常使役,支持多从机功能码通信及从机寄存器写入.pdf
Simulink永磁同步直驱风机PMSG一次调频离散模型:含虚拟惯性与下垂控制,可扩展至光伏储能研究.pdf
VSG仿真、并网与离网运行仿真、预同期并网控制及虚拟同步机逆变器仿真.pdf
VIC水文模型全程视频教学指导.pdf
vrep_coppeliasim+matlab机器人轨迹控制仿真:利用matlab读取轨迹并控制机械臂在墙上绘图的详细学习示例.pdf
2000-2022年上市公司行业异质性数据(技术密集型、劳动密集型、资本密集型)(含原始数据和处理代码) 1、时间:2000-2022年 2、指标:股票代码、年份、股票简称、统计日期、行业名称、行业代码、成立日期、上市日期、所在省份、所在城市、上市状态、保留两位行业代码、保留一位行业代码、高科技为1,非高科技为0、重污染为1,非重污染为0、制造业为1,非制造业为0、劳动密集型为1,资本密集型为2,技术密集型为3 3、来源:csmar 4、根据2012年中国证监会行业划分是否高科技、是否重污染、是否制造业、是否劳动密集型、资本密集型、技术密集型。 5、内容:包括原始数据、处理代码和计算结果
TMS320F28335电机控制程序:BLDC、PMSM无感有感及异步VF程序源代码与开发资料大全.pdf
tc275、s12x、s32k144基于CANoe的UDS诊断数据库CDD文件及CAPL Boot上位机、下位机程序移植说明文档.pdf
STM32系列通信透传技术:以太网、串口、CAN透传及OBD协议解析.pdf
STM32开发:IIR带阻滤波器设计与实现.pdf
UG后处理:CNC西门子828D后处理与西门子后处理工厂实战自用.pdf
MYSQL深入学习总结.pdf
Stewart六自由度平台反解算法 C#.pdf
1、文件说明: Centos8操作系统vim-ale-3.3.0-1.el8.rpm以及相关依赖,全打包为一个tar.gz压缩包 2、安装指令: #Step1、解压 tar -zxvf vim-ale-3.3.0-1.el8.tar.gz #Step2、进入解压后的目录,执行安装 sudo rpm -ivh *.rpm
tc275、s12x和s32k144的Boot程序及UDS故障诊断与Bootloader移植的Python自制上位机源码.pdf
SSA-CNN-LSTM时间序列预测(Matlab)_ 麻雀算法优化卷积长短期记忆网络.pdf
UI篇:C#工控上位机Chart控件实现与展示.pdf
SRM12-8开关磁阻电机,功率2200w,额定转速3450rpm.pdf