宣传不做低头族,红领巾心向党手抄报,狼行水浒
题目：
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
*/
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论