【构造共轭函数+矩阵快速幂】HDU 4565 So Easy! (2013 长沙赛区邀请赛)

本文主要是介绍【构造共轭函数+矩阵快速幂】HDU 4565 So Easy! (2013 长沙赛区邀请赛),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【题目链接】 :click here~~

【题目大意】:

 A sequence Sn is defined as:


Where a, b, n, m are positive integers.┌x┐is the ceil of x. For example, ┌3.14┐=4. You are to calculate Sn.
  You, a top coder, say: So easy! 

【解题思路】

给一张神图,推理写的灰常明白了,关键是构造共轭函数,这一点实在是要有数学知识的理论基础,推出了递推式,接下来就是矩阵的快速幂了。

给个大神的链接:构造类斐波那契数列的矩阵快速幂

神图:click here~~

代码:

/*
* Problem: HDU No.4565
* Running time: 62MS
* Complier: G++
* Author: javaherongwei
* Create Time: 9:55 2015/9/21 星期一
*/#include <bits/stdc++.h>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>using namespace std;
typedef long long LL;
const LL siz=2;          // max size of the matrix,
#define MODD(a,b) (((a%b)+b)%b)LL A,B,N,M,ret;
struct mut
{LL mat[siz][siz];mut(){memset(mat,0,sizeof(mat));}void init(LL a,LL b,LL c,LL d){mat[0][0]=a;mat[0][1]=b;mat[1][0]=c;mat[1][1]=d;}mut operator *(const mut &c){mut res;for(int i=0; i<siz; ++i){for(int k=0; k<siz; ++k){for(int j=0; j<siz; ++j){res.mat[i][j]=MODD(res.mat[i][j]+mat[i][k]*c.mat[k][j],M);}}}return res;}
}AC;mut poww(LL n)
{mut ans;ans.init(1,0,0,1);while(n){if(n&1) ans=ans*AC;n>>=1;AC=AC*AC;}return ans;
}int main()
{while(~scanf("%lld %lld %lld %lld",&A,&B,&N,&M)){if(N<=1){printf("%lld\n",2*A%M);}else{AC.init(2*A,B-A*A,1,0);mut ans=poww(N-1);printf("%lld\n",MODD(2*A%M*ans.mat[0][0]+2*ans.mat[0][1],M));}} return 0;
}

这篇关于【构造共轭函数+矩阵快速幂】HDU 4565 So Easy! (2013 长沙赛区邀请赛)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

MySQL中COALESCE函数示例详解

《MySQL中COALESCE函数示例详解》COALESCE是一个功能强大且常用的SQL函数,主要用来处理NULL值和实现灵活的值选择策略,能够使查询逻辑更清晰、简洁,:本文主要介绍MySQL中C... 目录语法示例1. 替换 NULL 值2. 用于字段默认值3. 多列优先级4. 结合聚合函数注意事项总结C

Win32下C++实现快速获取硬盘分区信息

《Win32下C++实现快速获取硬盘分区信息》这篇文章主要为大家详细介绍了Win32下C++如何实现快速获取硬盘分区信息,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 实现代码CDiskDriveUtils.h#pragma once #include <wtypesbase

Spring AI与DeepSeek实战一之快速打造智能对话应用

《SpringAI与DeepSeek实战一之快速打造智能对话应用》本文详细介绍了如何通过SpringAI框架集成DeepSeek大模型,实现普通对话和流式对话功能,步骤包括申请API-KEY、项目搭... 目录一、概述二、申请DeepSeek的API-KEY三、项目搭建3.1. 开发环境要求3.2. mav

Python如何快速下载依赖

《Python如何快速下载依赖》本文介绍了四种在Python中快速下载依赖的方法,包括使用国内镜像源、开启pip并发下载功能、使用pipreqs批量下载项目依赖以及使用conda管理依赖,通过这些方法... 目录python快速下载依赖1. 使用国内镜像源临时使用镜像源永久配置镜像源2. 使用 pip 的并

Java8需要知道的4个函数式接口简单教程

《Java8需要知道的4个函数式接口简单教程》:本文主要介绍Java8中引入的函数式接口,包括Consumer、Supplier、Predicate和Function,以及它们的用法和特点,文中... 目录什么是函数是接口?Consumer接口定义核心特点注意事项常见用法1.基本用法2.结合andThen链

SpringBoot集成图片验证码框架easy-captcha的详细过程

《SpringBoot集成图片验证码框架easy-captcha的详细过程》本文介绍了如何将Easy-Captcha框架集成到SpringBoot项目中,实现图片验证码功能,Easy-Captcha是... 目录SpringBoot集成图片验证码框架easy-captcha一、引言二、依赖三、代码1. Ea

MySQL 日期时间格式化函数 DATE_FORMAT() 的使用示例详解

《MySQL日期时间格式化函数DATE_FORMAT()的使用示例详解》`DATE_FORMAT()`是MySQL中用于格式化日期时间的函数,本文详细介绍了其语法、格式化字符串的含义以及常见日期... 目录一、DATE_FORMAT()语法二、格式化字符串详解三、常见日期时间格式组合四、业务场景五、总结一、

golang panic 函数用法示例详解

《golangpanic函数用法示例详解》在Go语言中,panic用于触发不可恢复的错误,终止函数执行并逐层向上触发defer,最终若未被recover捕获,程序会崩溃,recover用于在def... 目录1. panic 的作用2. 基本用法3. recover 的使用规则4. 错误处理建议5. 常见错

SpringBoot快速接入OpenAI大模型的方法(JDK8)

《SpringBoot快速接入OpenAI大模型的方法(JDK8)》本文介绍了如何使用AI4J快速接入OpenAI大模型,并展示了如何实现流式与非流式的输出,以及对函数调用的使用,AI4J支持JDK8... 目录使用AI4J快速接入OpenAI大模型介绍AI4J-github快速使用创建SpringBoot

SpringBoot整合easy-es的详细过程

《SpringBoot整合easy-es的详细过程》本文介绍了EasyES,一个基于Elasticsearch的ORM框架,旨在简化开发流程并提高效率,EasyES支持SpringBoot框架,并提供... 目录一、easy-es简介二、实现基于Spring Boot框架的应用程序代码1.添加相关依赖2.添