最新要闻
- 焦点速看:认知型通用大模型“360智脑”升级4.0,国内首发“文生视频”多模态功能
- 4连板联明股份:股价短期内涨幅明显高于上证指数及行业板块指数,但公司基本面未发生重大变化
- 多种矿物质元素 依能天然苏打水15瓶到手34.91元
- 世界快资讯:天气炎热 亚洲象开启“避暑模式”!网友:真羡慕了
- 超越《塞尔达传说:王国之泪》:《暗黑破坏神4》登顶英国周销量榜-新资讯
- 国产AI天花板!讯飞星火iOS内测版上线:已覆盖PC、手机等主流系统 短讯
- 微资讯!地表67℃!火焰山进入炙烤模式:景区为游客增配防暑药品
- 因为余华的一封信,莫言要去东澳岛读书了
- 科创浪潮奔涌大湾区
- PDF问世30周年 每年6月15日成“PDF日”
- 中国空间站美景请查收!央视解析全新构型:三舱三船
- 最高额外降温3℃:猫头鹰针对AMD AM5插槽CPU推出散热支架-热门
- 世界观天下!苹果蝉联2023年凯度BrandZ最具价值全球百强榜首:腾讯跻身十强
- 中国自研唯一入选项目!《王者荣耀亚运版本》发布:共计63个英雄
- 毕马威:力争在2030年将毕马威全球的直接和间接碳排放在2019年基础上减半 今日热议
- 世界今热点:层层梯田上红山荞麦播种忙 全产业链带动农民增收
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
[SDOI2008] 递归数列
题面
一个由自然数组成的数列按下式定义:
对于 \(i \le k\):\(a_{i}= b_{i}\)。
【资料图】
对于 \(i > k\):\(\displaystyle a_{i}= \sum_{j=1}^{k}{c_{j} \times a_{i-j}}\)。
其中 \(b_{1\dots k}\) 和 \(c_{1\dots k}\) 是给定的自然数。
写一个程序,给定自然数 \(m \le n\),计算 \(\left( \sum_{i=m}^{n}{a_{i}} \right) \bmod p\)。
\(1 \le k \le 15\),\(1 \le m \le n \le 10^{18}\),\(0 \le b_{i},c_{i} \le 10^{9}\),\(p \le 10^{8}\)。
题解
因为 \(k\) 很小,\(n, m\) 很大,不难想到矩阵加速递推。
根据 \(\displaystyle a_{i}= \sum_{j=1}^{k}{c_{j} \times a_{i-j}}\),所以我们的矩阵应该至少是一个 \(1 \times k\) 的矩阵,可以列出初始矩阵:
\[\begin{bmatrix}a_k & a_{k - 1} & \cdots & a_2 & a_1\end{bmatrix}\]其下一个转移则为:
\[\begin{bmatrix}a_{k + 1} & a_{k} & \cdots & a_3 & a_2\end{bmatrix}\]根据递推式可以列出转移矩阵:
\[\begin{bmatrix}c_1 & 1 & 0 & \cdots & 0\\c_2 & 0 & 1 & \cdots & 0\\\vdots & \vdots & \vdots & \ddots & 0\\c_n & 0 & 0 & \cdots & 1\end{bmatrix}\]这样我们就可以在 \(\displaystyle \mathcal{O}(K^2logN)\) 的时间里递推出 \(a_n\) 的值。但是我们回顾题意要求求出的值:
\[G(n, m) = \left( \sum_{i=m}^{n}{a_{i}} \right) \bmod p\]我们可以设 \(\displaystyle Sum(n) = \sum_{i = 1}^{n}a_i\) ,可以发现:
\[G(n, m) = Sum(n) - Sum(m - 1)\]所以我们可以在矩阵加速的时候一起处理出来 \(Sum(n)\),令我们的初始矩阵扩充为:
\[\begin{bmatrix}a_k & a_{k - 1} & \cdots & a_2 & a_1 & Sum(k - 1)\end{bmatrix}\]其下一个转移则为:
\[\begin{bmatrix}a_{k + 1} & a_{k} & \cdots & a_3 & a_2 & Sum(k)\end{bmatrix}\]考虑到 \(Sum(n) = Sum(n - 1) + a_n\),可以得到扩充后的转移矩阵为:
\[\begin{bmatrix}c_1 & 1 & 0 & \cdots & 0 & 1\\c_2 & 0 & 1 & \cdots & 0 & 0\\\vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\c_{n - 1} & 0 & 0 & \cdots & 0 & 0\\c_n & 0 & 0 & \cdots & 1 & 1\end{bmatrix}\]这样我们就可以在 \(\displaystyle \mathcal{O}(K^2logN)\) 的时间里解决这道题。
Code
//Luogu - P2461#includetypedef long long valueType;typedef std::vector ValueVector;valueType MOD_;valueType const &MOD = MOD_;class Matrix {public: typedef long long valueType; typedef valueType &reference; typedef size_t sizeType; typedef std::vector Row; typedef std::vector Container; valueType MOD = ::MOD; enum TYPE : int { EMPTY = 0, UNIT = 1 };protected: sizeType _row_, _column_; Container data;public: Matrix(sizeType row, sizeType column) : _row_(row), _column_(column), data(_row_) { for (auto &iter: data) iter.resize(column, 0); }; sizeType row() const { return _row_; } sizeType column() const { return _column_; } void set(TYPE type) { for (auto &iter: data) { std::fill(iter.begin(), iter.end(), 0); } if (type == EMPTY) return; if (type == UNIT) for (sizeType i = 0, end = std::min(_row_, _column_); i < end; ++i) data[i][i] = 1; } reference operator()(sizeType i, sizeType j) { if (i > this->_row_ || j > this->_column_) throw std::out_of_range("Too Large."); if (i == 0 || j == 0) throw std::out_of_range("0 index access."); return std::ref(data[i - 1][j - 1]); } Matrix operator+(const Matrix &T) const { if (this->_row_ != T._row_ || this->_column_ != T._column_) throw std::range_error("Illegal operation."); Matrix result(this->_row_, this->_column_); for (sizeType i = 0; i < this->_row_; ++i) for (sizeType j = 0; j < this->_column_; ++j) result.data[i][j] = (this->data[i][j] + T.data[i][j]) % MOD; return result; } Matrix operator*(const Matrix &T) const { if (this->_column_ != T._row_) throw std::range_error("Illegal operation."); Matrix result(this->_row_, T._column_); for (sizeType i = 0; i < this->_row_; ++i) { for (sizeType k = 0; k < this->_column_; ++k) { valueType r = this->data[i][k]; for (sizeType j = 0; j < T._column_; ++j) result.data[i][j] = (result.data[i][j] + T.data[k][j] * r) % MOD; } } return result; } Matrix operator^(valueType x) const { if (x < 1) throw std::range_error("Illegal operation."); Matrix result(this->_row_, this->_column_); Matrix base = *this; result.set(UNIT); while (x) { if (x & 1) result = result * base; base = base * base; x = x >> 1; } return result; } friend std::ostream &operator<<(std::ostream &os, const Matrix &T) { for (sizeType i = 0; i < T._row_; ++i) for (sizeType j = 0; j < T._column_; ++j) os << T.data[i][j] << " \n"[j == T._column_ - 1]; return os; } friend std::istream &operator>>(std::istream &os, Matrix &T) { for (sizeType i = 0; i < T._row_; ++i) for (sizeType j = 0; j < T._column_; ++j) os >> T.data[i][j]; return os; }};int main() {valueType K, M, N;std::cin >> K;ValueVector B(K + 30, 0), C(K + 30, 0);for(int i = 1; i <= K; ++i)std::cin >> B[i];for(int i = 1; i <= K; ++i)std::cin >> C[i];std::cin >> M >> N >> MOD_;for(int i = 1; i <= K; ++i) {B[i] %= MOD;C[i] %= MOD;}Matrix ans(1, K + 1), base(K + 1, K + 1);ans.set(Matrix::EMPTY);base.set(Matrix::EMPTY);for(int i = 1; i <= K; ++i)base(i, 1) = C[i];for(int i = 2; i <= K; ++i)base(i - 1, i) = 1;base(1, K + 1) = base(K + 1, K + 1) = 1;for(int i = 1; i <= K; ++i)ans(1, K + 1 - i) = B[i];ans(1, K + 1) = std::accumulate(B.begin() + 1, B.begin() + K, 0) % MOD;valueType resultN = 0, resultM = 0;++N;if(N > K) {Matrix MatrixN = ans * (base ^ (N - K));resultN = MatrixN(1, K + 1);} else {resultN = std::accumulate(B.begin() + 1, B.begin() + N, 0);}if(M > K) {Matrix MatrixM = ans * (base ^ (M - K));resultM = MatrixM(1, K + 1);} else {resultM = std::accumulate(B.begin() + 1, B.begin() + M, 0);}valueType result = resultN - resultM;result = (result % MOD + MOD) % MOD;std::cout << result << std::flush;return 0;}
关键词:
[SDOI2008] 递归数列
【全球播资讯】ssh免密登录、服务器安全
烷基计数
风口上的AIGC,技术岗动不动年薪百万,甚至重金难求? 天天新消息
MegEngine 使用小技巧:如何做 MegCC 的模型性能评测
焦点速看:认知型通用大模型“360智脑”升级4.0,国内首发“文生视频”多模态功能
4连板联明股份:股价短期内涨幅明显高于上证指数及行业板块指数,但公司基本面未发生重大变化
多种矿物质元素 依能天然苏打水15瓶到手34.91元
世界快资讯:天气炎热 亚洲象开启“避暑模式”!网友:真羡慕了
超越《塞尔达传说:王国之泪》:《暗黑破坏神4》登顶英国周销量榜-新资讯
国产AI天花板!讯飞星火iOS内测版上线:已覆盖PC、手机等主流系统 短讯
微资讯!地表67℃!火焰山进入炙烤模式:景区为游客增配防暑药品
FTL没有映射,跟发工资没有钱有什么区别 要闻
【全球新要闻】奇妙敏捷之旅·青岛站,现场燃爆了!
联盟送福利:云上掘金,开启你收入的第二增长曲线 全球新视野
机器硬件监控,最简单的方案,没有之一
因为余华的一封信,莫言要去东澳岛读书了
恒生指数14日收跌0.58%结束五连涨
科创浪潮奔涌大湾区
PDF问世30周年 每年6月15日成“PDF日”
中国空间站美景请查收!央视解析全新构型:三舱三船
最高额外降温3℃:猫头鹰针对AMD AM5插槽CPU推出散热支架-热门
世界观天下!苹果蝉联2023年凯度BrandZ最具价值全球百强榜首:腾讯跻身十强
中国自研唯一入选项目!《王者荣耀亚运版本》发布:共计63个英雄
毕马威:力争在2030年将毕马威全球的直接和间接碳排放在2019年基础上减半 今日热议
世界时讯:SpringBoot中Redis的基础使用
利用 PHP 特性绕 WAF 测试 环球聚看点
linux-DNS域名解析
世界即时看!2种GaussDB(DWS)查看作业运行信息方式
收评:两市窄幅波动沪指微跌0.14% CPO概念股领涨 大消费主题反弹
热头条丨【新华500】新华500指数(989001)14日涨0.03%
世界今热点:层层梯田上红山荞麦播种忙 全产业链带动农民增收
【当前独家】AMD自杀式降价 讯景RX 7900 XT显卡到手5299元(首发7399)
男生说猫屎臭被头上扣饭?官方回应:已经处理
天天滚动:与K60 Ultra同台发!Redmi 2K新平板曝光:只要千元
外卖小哥从10多米高大桥跳水救人:见义勇为获奖3万、免费上大学
焦点热讯:中国第一条时速350铁路明日调图:动车组重联 运力翻倍
2023内蒙古师范大学附属中学英才计划招生简章
618大促|解析平台、商家和消费者必须面对的三大风险
【技术积累】Python中的NumPy库【二】|天天滚动
全球快资讯丨Springboot定时任务集成shedLock锁
今日热搜:开放中国依然是外商投资高地
每日动态!晋升第一人口大国后 印度将成为全球第一大手机市场:多谢苹果
不是录播!梅西即将在淘宝开启首次直播
华为又背锅?理想粉丝暗指华为发动舆论攻击:李想出面澄清
亚运会倒计时101天!杭州开通“亚运号”定制专列
国内最畅销SUV排名出炉:特斯拉Model Y反超比亚迪宋Plus拿下第一
天天快看点丨大文件上传功能在标签服务的简单应用和代码实现
Aurelia教程_编程入门自学教程_菜鸟教程-免费教程分享
让电池新规为电动自行车加把“安全锁” 全球热点评
全球动态:21℃室温超导成果被美院士宣称复现!南大教授:有3点质疑
全球报道:吉利高管评理想学华为:华为是时代的产物 但时代变了
全球今日报丨Vision Pro商标被华为注册!专家:苹果要么求华为和解 要么中国市场改名
王鸿薇反击林飞帆退选还推责任 毫无担当 每日视点
快看:0-500公里仅需20.16秒!布加迪火流星正式亮相勒芒赛场
锐龙7 7800X3D搭配A620主板实测:游戏性能依旧胜过i9-13900KS
能打过理想L7?丰田新款汉兰达上市:26.88万起-新资讯
焦点热讯:Nothing Phone (2) 定档7月11日:比亚迪代工
世界热讯:无惧A卡狠降价!英伟达RTX 4060国内上市时间曝光:2399元秒抢光?
理想汽车在重庆成立销售新公司,注册资本1000万|世界观天下
【世界速看料】读发布!设计与部署稳定的分布式系统(第2版)笔记02_停飞的代码异常
每日消息!经典webshell流量特征
华洋赛车北交所IPO成功过会:产品进入美国等50余个国家和地区 参与多项标准起草
全球规模最大!京东亚洲一号第100亿件智能包裹下线
短睡眠者可能“天赋异禀”:每天只需睡四五个小时
东莞暴雨 外卖小哥摔倒人车被水冲走:市民合力营救
最新快讯!特斯拉换电池价格曝光:最贵24.6万元一块 能买一辆奥迪
特斯拉Model Y在上海一大学完全拆解 沉浸教学“三电”原理
环球热点评!word文档如何打千分号 千分号在word上怎么打
数位 DP
【全球时快讯】深度学习应用篇-元学习[13]:元学习概念、学习期、工作原理、模型分类等
直播app源码技术之直播间内消息发送与接收的实现-世界今日讯
真实案例:Feign 切换 okhttp 无法生效,被老大骂的有点慌!
美国CPI进入下行趋势 黄金期货继续维持震荡 全球快看点
李想:很多友商那仨瓜俩枣的销量有啥可干的|天天速讯
男子熬夜喝冰镇饮料被送进ICU 医生从血里抽出一袋油脂:超标200倍 全球看点
环球讯息:西安现最牛司机 车尾标语3月撞7次!奔驰大G、奥迪都被撞过
世界新消息丨美国发布临时禁令:微软收购动视暴雪再次受阻
天津两处居民楼爆炸,致3死多伤!嫌疑人被抓获,作案工具是_环球新资讯
Canvas_绘制线段、圆形、文本、图像、视频、处理图像数据
【项目管理解决方案】上海道宁与Synami帮助您统一所有项目级别的信息,并使所有人轻松访问
Zabbix“专家坐诊”第195期问答汇总_当前看点
XenServer 7 GUI 虚拟机(VM)上的屏幕分辨率怎么提高? 环球简讯
入侵无线App盗用户资料 40岁男子被捕|观察
天天时讯:有无眉毛哪个更好看?哪吒CEO:“去掉眉毛”的哪吒GT将上市
携程梁建章建议:生三胎每月给五六千 给到18岁为止 速讯
15英寸MacBook Air首销破发!渠道价比官网便宜1000多|全球速看
新能源重卡 为何终将颠覆燃油重卡?
华为开发者大会2023早鸟票开售 498元起-全球最资讯
速讯:注意!绿心环线多路段将进行抓拍
MySQL性能分析及工具使用_今日热讯
演唱会买到“柱子票”,可以有更好的解决办法 全球要闻
PCIe 6.0还没用上:PCIe 7.0这就来了!x16速度高达512GB/s-世界滚动
175W功耗释放稳压64℃!铭瑄RTX 4060 Ti iCraft OC8G瑷珈显卡评测:二次元秀肌肉-环球观天下
为保护迎客松不让当地用户买木头、绿植?黄山回应
颠覆物理学!美国院士称复现室温超导 这还是骗局?
关注: 信用卡逾期停息挂账申请有什么条件?网贷逾期有什么影响?_当前热点
融创优化强制可转债方案 境外债重组方案获约近九成债权人支持
【读财报】游戏ETF透视:华夏基金规模、业绩领跑 华泰柏瑞、浦银安盛基金份额萎缩
南京十四所招聘官网_南京十四所_天天快资讯