/* * [题意] * 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; }
相关推荐
教程来自HDU 的ACM教案,非常好的一个资料
教程来自HDU 的ACM教案,非常好的一个资料
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
可拆卸核心板滤波电容电源指示灯排针复位F103--R10不焊F207--R9不焊第19引脚F103--C4焊0欧姆,C3不焊Tuesday, August 31
排母,核心板接口ADC 电位器扩展接口,预留模拟量Tuesday, August 31, 2021Tuesday, August 31, 2021Tuesday
ACM题库,一些题目和答案,以及解题报告,传上来共享
第一章 功能简介本章介绍HDU-EID-V2开发板的功能,使大家对该开发板的功能及特点有个基本了解。1. 处理器( MCU)HDU-EID-V2 开发板的处理器
基础算法类 ACM 入门 杭电OJ 11页题目题解,算法入门的时候刷题可以参考 搜集整理起来了比单个去搜题解方便快捷
HDU 里面的2000~2099道题目的源码。谢谢支持
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电OnlineJudge 200-2099的解题报告
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
很多经典的杭电oj与poj习题的ac代码与详解!全部ac,决对没有错误的代码!
杭电ACM2000-2099题的解题报告
HDU 1010-2500解题报告,ACMer可以借鉴一下
hdu2000-2014ac代码,虽然只有几道,但都是简单的
杭州电子科技大学ACM Steps中Chapter One-Section One的答案集。不要直接抄哦~~ 如需题解请上我的博客~ 博客地址呈上:http://blog.csdn.net/xu_zh