Recursive sequence(HDU5950 矩阵快速幂)
题目:
farmer john likes to play mathematics games with his n cows. recently, they are attracted by recursive sequences. in each turn, the cows would stand in a line, while john writes two positive numbers a and b on a blackboard. and then, the cows would say their identity number one by one. the first cow says the first number a and the second says the second number b. after that, the i-th cow says the sum of twice the (i-2)-th number, the (i-1)-th number, and i4i4. now, you need to write a program to calculate the number of the n-th cow in order to check if john’s cows can make it right.
input:
farmer john likes to play mathematics games with his n cows. recently, they are attracted by recursive sequences. in each turn, the cows would stand in a line, while john writes two positive numbers a and b on a blackboard. and then, the cows would say their identity number one by one. the first cow says the first number a and the second says the second number b. after that, the i-th cow says the sum of twice the (i-2)-th number, the (i-1)-th number, and i4i4. now, you need to write a program to calculate the number of the n-th cow in order to check if john’s cows can make it right.
output:
for each test case, output the number of the n-th cow. this number might be very large, so you need to output it modulo 2147493647.
hint:
in the first case, the third number is 85 = 2*1+2+3^4.
in the second case, the third number is 93 = 2*1+1*10+3^4 and the fourth number is 369 = 2 * 10 + 93 + 4^4.
题意:
奶牛报数,先给两个数a和b,分别是f[n-2],f[n-1],之后每头奶牛i报数为f[i-1] + 2 * f[i-2] + i^4;给出n,求din头奶牛要报的数字,对2147493647取余。
思路:
看到这个式子知道这是一个矩阵快速幂,然后开始推式子,在我给队友写出平方差公式来队友看到杨辉三角形式后后,就去推7*7的矩阵快速幂了,但因为刚刚学这个,但结束就挂死在这个题上了。
具体式子如下:
之后就是套裸的矩阵快速幂就好了,个人感觉做题补题真的是长知识最快的方法啊。补题的时候自己直接用矩阵来写麻烦的要死,就把矩阵放在一个结构体中,顺便方便很多。
代码:
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <queue> #include <map> #include <set> #include <vector> using namespace std; typedef long long ll; const ll mod = 2147493647; struct maxt { ll mp[8][8]; maxt() { for(int i = 1; i<=7; i++) { for(int j = 1; j<=7; j++) { mp[i][j] = 0; } } } } fp,tmp; int n,a,b,t; int read() { int res = 0; char op; op = getchar(); if(op>='0' && op<='9') { res = op-'0'; op = getchar(); } while(op>='0' && op<='9') { res = res*10 + op-'0'; op = getchar(); } return res; } void init() { for(int i = 1; i<=7; i++) { for(int j =1; j<=7; j++) { fp.mp[i][j] = 0; tmp.mp[i][j] = 0; } } fp.mp[1][1] = 1,fp.mp[2][1] = 1,fp.mp[2][2] = 1,fp.mp[7][6] = 1; fp.mp[3][1] = 1,fp.mp[3][2] = 2,fp.mp[3][3] = 1,fp.mp[4][1] = 1; fp.mp[4][2] = 3,fp.mp[4][3] = 3,fp.mp[4][4] = 1,fp.mp[5][1] = 1; fp.mp[5][2] = 4,fp.mp[5][3] = 6,fp.mp[5][4] = 4,fp.mp[5][5] = 1; fp.mp[6][5] = 1,fp.mp[6][6] = 1,fp.mp[6][7] = 2; tmp.mp[1][1] = 1,tmp.mp[2][1] = 3,tmp.mp[3][1] = 9,tmp.mp[4][1] = 27,tmp.mp[5][1] = 81,tmp.mp[6][1] = b,tmp.mp[7][1] = a; } maxt maxtcalc(const maxt& a,const maxt& b) { maxt t; for(int i = 1; i<=7; i++) { for(int j = 1; j<=7; j++) { t.mp[i][j] = 0; for(int k = 1; k<=7; k++) { t.mp[i][j] = (t.mp[i][j] + (a.mp[i][k]*b.mp[k][j]) % mod) % mod; } } } return t; } maxt qcalc(int x,maxt s) { maxt tmp; for(int i = 1; i<=7; i++) { tmp.mp[i][i] = 1; } while(x) { if(x&1) { tmp = maxtcalc(tmp, s); } s = maxtcalc(s, s); x>>=1; } return tmp; } int main() { t = read(); while(t--) { n = read(); a = read(); b= read(); if(n == 1) { printf("%d\n",a); continue; } if(n == 2) { printf("%d\n",b); continue; } if(n == 3) { printf("%d\n",81+2*a+b); continue; } n = n-2; init(); fp = qcalc(n,fp); maxt ans = maxtcalc(fp, tmp); printf("%lld\n",ans.mp[6][1]%mod); } return 0; } /* 样例输入: 2 3 1 2 4 1 10 样例输出: 85 369 */
上一篇: 显卡现在可以下山了吗? 再等等
下一篇: 日本推出低价云计算型列车运行管理系统
推荐阅读
-
矩阵乘法(二):利用矩阵快速幂运算完成递推
-
FZU2018级算法第一次作业 1.1fibonacci (矩阵快速幂)
-
2018年湘潭大学程序设计竞赛G又见斐波那契(矩阵快速幂)
-
HDU 2256Problem of Precision(矩阵快速幂)
-
洛谷P1397 [NOI2013]矩阵游戏(十进制矩阵快速幂)
-
POJ3233Matrix Power Series(矩阵快速幂)
-
BZOJ1898: [Zjoi2005]Swamp 沼泽鳄鱼(矩阵快速幂)
-
BZOJ2476: 战场的数目(矩阵快速幂)
-
矩阵乘法(四):分析问题,确定递推式,采用矩阵快速幂求解
-
矩阵乘法(二):利用矩阵快速幂运算完成递推