HDU 4686 Arc of Dream (矩阵快速幂)

题意:An Arc of Dream is a curve defined by following function:
在这里插入图片描述
where
a 0 = A0
a i = a i-1 * AX+AY
b 0 = B0
b i = b i-1 * BX+BY
给出n,A0,AX,AY,B0,BX,BY,What is the value of AoD(N) modulo 1,000,000,007?

题解:矩阵快速幂
数据范围很恶心,先要对原数据取模,对于两个数的乘法也要马上取模。
题目给出的转移关系很明确,由于要求和,可得转移矩阵为
T=[AX0AY000BXBY0000100AXBYBXAYAYBYAXBX0AXBYBXAYAYBYAXBX1]T= \left[ \begin{matrix} AX & 0 & AY&0&0 \\ 0 & BX & BY&0&0 \\ 0&0&1&0&0\\ AX*BY&BX*AY&AY*BY&AX*BX&0\\ AX*BY&BX*AY&AY*BY&AX*BX&1\\ \end{matrix} \right]
初始矩阵为
ma=[A0(ai1)B0(bi1)1A0B0((ai1)(bi1))A0B0(AoD)]ma= \left[ \begin{matrix} A0(a_{i-1}) \\ B0(b_{i-1}) \\ 1 \\ A0*B0((a_{i-1})*(b_{i-1}))\\ A0*B0(AoD)\\ \end{matrix} \right]

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<fstream>
#include<set>
#include<map>
#include<sstream>
#include<iomanip>
#define ll long long
using namespace std;
//矩阵快速幂
const int mod = 1e9 + 7;
struct matrix {
    ll mat[5][5];
    matrix() { memset(mat, 0, sizeof(mat)); }
    matrix operator * (const matrix& b)const {
        matrix ans;
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                ans.mat[i][j] = 0;
                for (int k = 0; k < 5; k++) {
                    ans.mat[i][j] = (ans.mat[i][j] + mat[i][k] * b.mat[k][j] % mod + mod) % mod;
                }
            }
        }
        return ans;
    }
};
matrix q_pow(matrix a, ll b) {
    matrix ans;
    memset(ans.mat, 0, sizeof(ans.mat));
    for (int i = 0; i < 5; i++) ans.mat[i][i] = 1;
    while (b) {
        if (b & 1) ans = ans * a;
        b >>= 1;
        a = a * a;
    }
    return ans;
}
ll n, a0, ax, ay, b0, bx, by;
int main() {
    while (~scanf("%lld%lld%lld%lld%lld%lld%lld", &n, &a0, &ax, &ay, &b0, &bx, &by)) {
        a0 %= mod, ax %= mod, ay %= mod, b0 %= mod, bx %= mod, by %= mod;
        if (n == 0) {
            puts("0");
        }
        else if (n == 1) {
            printf("%lld\n", a0 * b0 % mod);
        }
        else {
            matrix ma;
            ma.mat[0][0] = ax % mod, ma.mat[0][2] = ay % mod;
            ma.mat[1][1] = bx % mod, ma.mat[1][2] = by % mod;
            ma.mat[2][2] = 1;
            ma.mat[3][0] = ax * by % mod, ma.mat[3][1] = bx * ay % mod, ma.mat[3][2] = ay * by % mod, ma.mat[3][3] = ax * bx % mod;
            ma.mat[4][0] = ax * by % mod, ma.mat[4][1] = bx * ay % mod, ma.mat[4][2] = ay * by % mod, ma.mat[4][3] = ax * bx % mod, ma.mat[4][4] = 1;
            ma = q_pow(ma, n - 1);
            ll ans = ma.mat[4][0] * a0 % mod + ma.mat[4][1] * b0 % mod + ma.mat[4][2] + ma.mat[4][3] * (a0 * b0 % mod) % mod + a0 * b0 % mod;
            printf("%lld\n", ans % mod);
        }
    }
	return 0;
}

热门文章

暂无图片
编程学习 ·

数据结构学习笔记-队列长度的计算

1.通用计算公式:l=(rear-front+n)%n其中:l为当前队列的长度rear为队列尾指针front为队列头指针n为队列可容纳的元素总数(即队列大小)2.公式解析队列中存在一种特殊情况:循环队列,一般定义循环队列的头指针front和尾指针rear均指向队列下标为0的位置,此时front=rear&…
暂无图片
编程学习 ·

JS面试题

霖呆呆的近期面试128题汇总(含超详细答案) | 掘金技术征文 由浅入深,66条JavaScript面试知识点 2020 前端面试 | 第一波面试题总结 2020 前端面试 | 第二波面试题总结 window.onload和$(document).ready()区别 window.onload必须等到页面内的所有元素加载完毕后才能执行 所有元…
暂无图片
编程学习 ·

数据结构与数据类型

数据结构与数据类型数据类型是面向应用领域的具体化,同时面向计算机系统底层是为了确定分配的内存容量的大小。 在C,JAVA等静态类型的编程语言中,编译器根据数据类型,提前在内存的进程的栈中分配特定 大小的空间。C 的malloc,和Java的new是动态分配大块内存的,提前在内存…
暂无图片
编程学习 ·

python读取excel文件(xlrd)

调包import xlrd打开文件data = xlrd.open_workbook(文件名.xlsx)查看页名print(data.sheet_names())输出sheet1、sheet2等页名,一般用不上,因为可以用下表取页获取某页sheet = data.sheet_by_name(sheet1) sheet = data.sheet_by_index(0)两个方法都行,一般用第二个,因为第…
暂无图片
编程学习 ·

坚强奋斗的后浪们,后浪们的逆风翻盘之路。

逆风5.4日B站播出了后浪,视频伴随着激情澎湃的音乐、华丽无比的台词、精英人士的代言,可以说很振奋人心。但是观看后,网上却有着两种不同的声音,分别是乐观与悲观。当然伴随着疫情肆虐,悲观的声音反而是最响亮。90后们更是看的焦躁不安、时逢逆风,如何翻盘? 逆风论点:通…
暂无图片
编程学习 ·

活动目录的备份和恢复

活动目录的备份和恢复AD的备份和恢复AD回收站说明启用回收站功能演示AD回收站AD活动目录的备份和还原AD活动目录的备份安装Windows Server Backup工具添加角色和功能开始之前-安装类型-服务器选择-服务器角色,默认下一步功能确认结果开始备份AD活动目录AD活动目录的恢复重启按…
暂无图片
编程学习 ·

HCIP-RS-H12-221题库以及解析(部分)

不定期更新题库和解析,原题库不包含解析,解析有错误或不对的地方欢迎评论指正 1.由于属性AS-path不能在AS内起作用,所以规定BGP路由器不会宣告任何从IBGP对等体来的更新信息给其对等体 (√) 2.通过重发布命令注入BGP的路由,其orgin的属性为incomplete (√) 3.自制系统…
暂无图片
编程学习 ·

防火墙中的DMZ区域,Trust区域,Untrust区域

** 区域的作用: ** 1.安全策略都基于区域实施 2.在同一区域内部发生的数据流动是不存在风险的,不需要实施任何安全策略。 只有当不同安全区域之间发生数据流动时,才会触发设备的安全检查,并实施相应的安全策略。 3.一个接口只能属于一个区域,而一个区域可以有多个接口。 *…
暂无图片
编程学习 ·

移动端如何使用fidder代理访问测试

1. 保证自己本地电脑能访问测试环境(配置host),如图2. 电脑安装fiddeer:https://blog.csdn.net/BGONE/article/details/93007613 3. 修改fidder配置 菜单Tools—Options—Connections,如图1点击allow remote conputers to connect->OK4. 手机配置代理(亲测安卓、IOS都可…
暂无图片
编程学习 ·

【漏洞通告】Treck TCP/IP协议库“ Ripple20”漏洞通告

【漏洞通告】Treck TCP/IP协议库“ Ripple20”漏洞通告 威胁对抗能力部 [绿盟科技安全情报](javascript:void(0)😉 昨天 通告编号:NS-2020-0039 2020-06-30TA****G: Treck、TCP/IP协议库、Ripple20漏洞危害: 攻击者利用此类漏洞,可造成拒绝服务、远程代码执行等。版本: 1…
暂无图片
编程学习 ·

JAVA学习之路(3) request的总结

文章目录引言Request对请求行数据的操作Request对请求头数据的操作Request对请求头数据的操作通用方式中文乱码问题请求转发 引言 在httpServlet类中,我们只需要调用doGet和doPost方法即可以实现对应的功能。对应这两个方法,有两个穿进去的参数对象,一个是response,一个是r…
暂无图片
编程学习 ·

Spring测试中的事务

目录 文章目录@Transactional @Transactional 1、测试方法加上该注解后事务自动回滚。 2、@BeforeEach与@AfterEach在测试方法的事务中执行 3、@BeforeTransactional与@AfterTransactional在事务执行之前之后执行;并且没有加@Transactional的测试方法不执行这两个注解下的方法…
暂无图片
编程学习 ·

MRTK开发资料整理

1. 认识MRTK 2. 创建第一个MRTK项目—学习MRTK SDK的导入和打包发布 3.1 创建用户界面并配置MRTK—学习更改默认配置(clone default profiles) 3.2 MRTK内置编辑器手势操作 4. 使用Solvers创建动态内容—使创建的物体始终位于视野中心或随手的位置而改变Solvers are componen…
暂无图片
编程学习 ·

mysql5.7安装

本篇文章介绍的是mysql5.7安装教程! 环境:Windows 类型:msi Mysql安装包可以去官网下载 mysql官网下载 也可以加入我们群聊下载(群文件mysql文件夹下) 另外,加入群聊也可以远程安装 文章目录mysql 5.7安装 准备安装包安装步骤第一步同意协议第二步选择手动安装第三步选择…
暂无图片
编程学习 ·

从 Android 源码分析自定义 View 相关知识点

以下源码来自于 Android P。onMeasure()MeasureSpecMeasureSpec 是 View 里的一个内部类,其用来表示 View 的测量模式和测量大小,代码如下:public static class MeasureSpec {/*** Creates a measure specification based on the supplied size and mode.** The mode must a…
暂无图片
编程学习 ·

Java语言基础(二)变量和数据类型

Java语言基础(二)二、变量和数据类型2.1 变量的基本概念2.2 变量的声明和使用2.3 变量使用是注意事项2.4 标识符的命名规则(笔试)关键字2.5 变量输入输出的案例实现2.6 变量输入输出案例的优化和手册介绍2.7 数据类型的分类2.8 常用的进制2.9 十进制与二进制之间的转换(1)正…
暂无图片
编程学习 ·

springboot添加一些全局异常处理

1.添加全局异常处理类 package com.iflytek.edu.hnezzhxy.common.base;import com.iflytek.edu.hnezzhxy.common.enums.ResponseCodeEnum; import com.iflytek.edu.hnezzhxy.util.ResponseResultUtil; import com.iflytek.edu.hnezzhxy.vo.ResultVO; import org.slf4j.Logger; …