[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] 递归数列 天天最新
-
脚踝滑膜炎的症状表现_脚踝疼痛是什么原因造成的 全球关注
-
中国人民财产保险股份有限公司金昌市分公司院内地坪维修项目成交公告
-
快播:螺纹钢是热轧带肋钢筋吗_急啊 螺纹钢 带肋钢筋和光圆钢筋三者有何区别
-
员工甲乙互殴,单位给甲赔付8000元。同一事情然后甲又把乙起诉法院判决乙给甲赔款10000元
-
汉阴县城关镇:守好地 种好田 护好粮|天天动态
-
可转债退市有了新“说法”:退市整理期首日不设涨跌幅 公募基金不能买入退市转债|环球新消息
-
观点:港股异动 | 博维智慧(01204)涨超6% 与澳门会展旅游业协会签订合作备忘录 推进脑机交互技术在展览中应用
-
当前快看:668001首页溜溜吧(668001 com)
-
2023伊春顶尖高中排名 哪些高中最好
-
全球球精选!德粤赑鑫黄斐斐:以策略逻辑为基础,以大数据策略为依托
-
今日快看!江苏森工国际贸易有限公司_关于江苏森工国际贸易有限公司简述
-
环球速读:法律规定房屋动迁怎么安置?
-
洪江市:“一网通办”优化企业服务-观察
-
超华科技:6月13日融资买入118.38万元,融资融券余额1.61亿元
-
如何富民强村?广东多地有了线索答案
-
疝气怎么治疗 疝气病的治疗方法有哪些药_疝气怎么治疗 疝气病的治疗方法有哪些
-
世界微头条丨对外汉语教师资格证报考条件知乎(对外汉语教师资格证报考条件)
-
央行政策利率齐降 传递稳增长信号
-
全国已收获冬小麦面积2.67亿亩 收获进度达87.7%
-
国投瑞银顺达纯债债券型证券投资基金分红公告
-
6月13日基金净值:华夏兴阳一年持有混合最新净值0.9371,涨0.54%|世界观焦点
-
红米k40游戏版孔位说明
-
服装家纺板块6月13日跌0.48%,XD日播时领跌,主力资金净流入8018.67万元-天天即时
-
i54200m与n5095哪个好_i54200m
-
联想电脑一体机价格表_联想电脑一体机
-
罗马诺:巴黎对姆巴佩的立场很明确,续约或者今夏离队 环球观焦点
-
天龙集团:6月12日公司高管王娜减持公司股份合计2万股
-
打造海上智慧油田的“信息大动脉”|全球热点评
-
用创意见证青春,用歌声唱响未来!看看这所大学的毕业季活动→
-
世界观热点:刘彦春为下半年打“call”:绩优股已非常便宜
-
金融服务“新市民”有力度更有温度
-
央行:5月末社会融资规模存量361.42万亿元 同比增长9.5%
-
全球快资讯:共读时刻|如何通过战略创新实现高水平增长?
-
概伦电子:两位股东拟合计减持不超过3%