题目链接:uva 10689 - Yet another Number Sequence
题目大意:给定斐波那契数列头两项,求的n项取模10m
解题思路:矩阵快速幂。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 5;
const int M[maxn+5] = {1, 10, 100, 1000, 10000};
int MOD;
struct Mat {
int arr[maxn][maxn];
Mat () {
memset(arr, 0, sizeof(arr));
}
Mat operator * (const Mat& u) {
Mat ret;
for (int k = 0; k < 2; k++) {
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
ret.arr[i][j] = (ret.arr[i][j] + arr[i][k] * u.arr[k][j]) % MOD;
}
return ret;
}
};
Mat pow_mat(Mat x, int n) {
Mat ret;
for (int i = 0; i < 2; i++)
ret.arr[i][i] = 1;
while (n) {
if (n&1)
ret = ret * x;
x = x * x;
n >>= 1;
}
return ret;
}
int main () {
int cas;
scanf("%d", &cas);
while (cas--) {
int a, b, n, m;
scanf("%d%d%d%d", &a, &b, &n, &m);
MOD = M[m];
Mat x;
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
x.arr[i][j] = 1;
x.arr[0][0] = 0;
if (n >= 1) {
Mat ans = pow_mat(x, n-1);
printf("%d\n", (ans.arr[1][0] * a % MOD + ans.arr[1][1] * b % MOD) % MOD);
} else
printf("%d\n", a);
}
return 0;
}
分享到:
相关推荐
memory networks, are extremely appealing for sequence-tosequence learning tasks. Despite their great success, they typically suffer from a fundamental shortcoming: they are prone to generate ...
论文《End-to-end Sequence Labeling via Bi-directional LSTM-CNNs-CRF》的代码实现
(译文)End-to-End Radio Traffic Sequence Recognition with Deep Recurrent Neural Networks
State-of-the-art sequence labeling systems traditionally require large mounts of task-specific knowledge in the form of hand-crafted features and data pre-processing.In this paper, we introduce a ...
Edward Grefenstette - Beyond Sequence to Sequence with Augmented RNNs
解决Invalid byte 1 of 1-byte UTF-8 sequence
next[i]的含义是在str[i]之前的字符串str[0...i]中,必须以str[i-1]结尾的后缀子串(不能包含str[0])与必须以str[0]开头的前
前端开源库-gulp-run-sequencegulp run sequence,已弃用-请改用run sequence:https://npmjs.org/package/run-sequence
磁共振成像经典教材
基于循环神经网络和注意力机制的Sequence-to-Sequence模型神经网络方法在信息抽取和自动摘要生成方面发挥了重要作用。然而,该方法不能充分利用文本的语言特征信息,且生成结果中存在未登录词问题,从而影响文本摘要...
HDU-1711 Number Sequence(KMP算法)For each test case, you should output one line wh
北大POJ1019-Number Sequence 解题报告+AC代码
机器学习之sequence to sequence learning。(Sequence Generation-----Hung-yi Lee 李宏毅.ppt)
(创建是因为我在使用纯JavaScript的解决方案时遇到了性能问题,例如: : ) 它是围绕iOS UIImageView.animationImages和Android AnimationDrawable的简单包装安装npm i --save react-native-image-sequence react-...
这是ten so r f lo w中sequence2sequence的那一章节,这里单独拿出来
字体,圈码类。适用于加圈脚注各用书稿论文文档排版。
Label-Free-DNA-Sequence-Detection-through-FRET-from-a-Fluorescent
基于数据库的分布式发号器-viemall-sequence基于数据库的分布式发号器-viemall-sequence基于数据库的分布式发号器-viemall-sequence基于数据库的分布式发号器-viemall-sequence基于数据库的分布式发号器-viemall-...
how to use ax Number Sequence
前端开源库-meteor-observe-sequence流星观测序列,空