关键词：
题意：f[1]=a,f[2]=b,f[i]=2f[i-2]+f[i-1]+i^4（i>=3），多组询问求f[n]对2147493647取模
N,a,b < 2^31
思路：重点在于i^4的处理
对于i转移矩阵中可以记录下它的0,1,2,3,4次项
i的幂又可以由i-1的幂运算得出，最后推出的系数是二项式展开的系数
试试新的矩乘模板
1 #include<cstdio> 2 #include<cstring> 3 #include<string> 4 #include<cmath> 5 #include<iostream> 6 #include<algorithm> 7 #include<map> 8 #include<set> 9 #include<queue> 10 #include<vector> 11 using namespace std; 12 typedef long long ll; 13 typedef unsigned int uint; 14 typedef unsigned long long ull; 15 typedef pair<int,int> PII; 16 typedef vector<int> VI; 17 #define fi first 18 #define se second 19 #define MP make_pair 20 #define N 2100000 21 #define MOD 2147493647 22 #define eps 1e-8 23 #define pi acos(-1) 24 const int MAXN=10; 25 26 int read() 27 28 int v=0,f=1; 29 char c=getchar(); 30 while(c<48||57<c) if(c==‘-‘) f=-1; c=getchar(); 31 while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar(); 32 return v*f; 33 34 35 36 struct matrix //矩阵类 37 38 int n,m; 39 ll data[MAXN][MAXN]; 40 ; 41 42 matrix ma,mb; 43 ll a,b,c,d,p,n; 44 45 matrix matrixMul(matrix a, matrix b) 46 47 matrix re; 48 if(a.m!=b.n) 49 50 printf("error "); 51 return re; 52 53 memset(re.data,0,sizeof(re.data)); 54 re.n = a.n; re.m = b.m; 55 for(int i = 1; i <= a.n; i++) 56 57 for(int j = 1; j <= a.m; j++) 58 59 if(a.data[i][j] == 0) continue; 60 for(int k = 1; k <= b.m; k++) 61 62 re.data[i][k] += (a.data[i][j] % MOD * b.data[j][k] % MOD) % MOD; 63 re.data[i][k] %= MOD; 64 65 66 67 return re; 68 69 70 matrix matrixPow(matrix a,int b) 71 72 matrix re; 73 if(a.n!=a.m) 74 75 printf("error2 "); 76 return re; 77 78 re.n=re.m=a.n; 79 memset(re.data,0,sizeof(re.data)); 80 for(int i=1;i<=re.n;i++) re.data[i][i]=1; 81 while(b) 82 83 if(b&1) re=matrixMul(re,a); 84 a=matrixMul(a,a); 85 b>>=1; 86 87 return re; 88 89 90 void inputMat(int n,int m,matrix &a,ll *b) 91 92 a.n = n; a.m = m; 93 for(int i = 1; i <= n; i++) 94 for(int j = 1; j <= m; j++) 95 a.data[i][j] = *(b + (i - 1) * m + (j - 1)); 96 97 98 void init() 99 ll pt[1][7] = b,a,16,8,4,2,1; 100 inputMat(1,7,ma,*pt); 101 ll pt2[7][7] = 1,1,0,0,0,0,0, 102 2,0,0,0,0,0,0, 103 1,0,1,0,0,0,0, 104 4,0,4,1,0,0,0, 105 6,0,6,3,1,0,0, 106 4,0,4,3,2,1,0, 107 1,0,1,1,1,1,1,; 108 inputMat(7,7,mb,*pt2); 109 110 111 int main() 112 113 int cas; 114 scanf("%d",&cas); 115 while(cas--) 116 117 scanf("%I64d%I64d%I64d",&n,&a,&b); 118 int i=3; 119 a%=MOD; 120 b%=MOD; 121 if(n == 1) 122 printf("%I64d ",a); 123 else if(n == 2) 124 printf("%I64d ",b); 125 else 126 127 128 init(); 129 ma=matrixMul(ma,matrixPow(mb,n-2)); 130 131 printf("%I64d ",ma.data[1][1]); 132 133 return 0; 134
recursivesequence（hdu5950矩阵快速幂）(代码片段)
题目：FarmerJohnlikestoplaymathematicsgameswithhisNcows.Recently,theyareattractedbyrecursivesequences.Ineachturn,thecowswouldstandinaline,whileJohnwritestwopositivenumbersaandbonablackboard.Andthen,theco 查看详情
hdu5950recursivesequence（矩阵快速幂）
RecursivesequenceTimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/65536K(Java/Others)TotalSubmission(s):1323 AcceptedSubmission(s):589ProblemDescripti 查看详情
hdu5950-recursivesequence(矩阵快速幂）
题目链接：Recursivesequence 题意：给出n头母牛，第一头报a，第二头报b，第i头报f[i-2]*2+f[i-1]+i^4,问第n头母牛报数多少 分析：N,a,b<2^31,果断矩阵快速幂，关键是要推出公式，公式如下，仅作参考1000000 ... 查看详情
5950recursivesequence(矩阵快速幂)
题意：递推公式Fn=Fn-1+2*Fn-2+n*n，让求Fn;析：很明显的矩阵快速幂，因为这个很像Fibonacci数列，所以我们考虑是矩阵，然后我们进行推公式，因为这样我们是无法进行运算的。好像有的思路，最后也没想出来，还是参考的大牛的博... 查看详情
hdu5950recursivesequence矩阵快速幂
http://acm.hdu.edu.cn/showproblem.php?pid=5950一开始以为i^4不能矩阵快速幂，但是结论是可以得，那么要怎么递推呢？矩阵快速幂的思路都是一样的，matrix_a*matrix_b^n其中，想要维护什么，就在matrix_a写，比如现在是F[n-1],F[n-2]，我想要递推... 查看详情
hdu5950recursivesequence递推+矩阵快速幂(2016acm/icpc亚洲区沈阳站)
RecursivesequenceTimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/65536K(Java/Others)TotalSubmission(s):249 AcceptedSubmission(s):140ProblemDescriptio 查看详情
hdu5950-recursivesequence-[矩阵快速幂加速递推][2016acm/icpc亚洲区沈阳站problemc](代码片段)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5950FarmerJohnlikestoplaymathematicsgameswithhisNcows.Recently,theyareattractedbyrecursivesequences.Ineachturn,thecowswouldstandinaline,whileJohnwritestw 查看详情
recursivesequencehdu-5950
Recursivesequence HDU-5950 题意：求 f(n) = f(n?1)+2*f(n?2)+n4，其中 f(1)=a,f(2)=b利用矩阵加速~比较坑的是mod=2147493647。。。。不是2147483647，用intWA了多次=_=||1#include<bits/stdc++.h>2usingnam 查看详情
hdu5950
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5950解题思路： AC代码：1#include<cstdio>2#include<cstring>34usingnamespacestd;5typedeflonglongll;6constllmod=2147493647;7structMatrix{8llmat[7][7];9 查看详情
hdu5950（矩阵快速幂）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5950题意：f(n)=f(n-1)+2*f(n-2)+n^4，f(1)=a,f(2)=b，求f(n)思路：对矩阵快速幂的了解仅仅停留在fib上，重现赛自己随便乱推还一直算错，快两个小时才a还wa了好几次....主要就是构造矩阵：(n+1)^4=... 查看详情
recursivesequencehdu-5950(代码片段)
RecursivesequenceHDU-5950题意：给你一个式子：f[n]=2f[n-2]+f[n-1]+n4给你f[1]和f[2]，给你一个n，求f[n]f[1],f[2],n<=231题解：很明显，矩阵快速幂，但是太久没做这种题，我都忘了怎么 查看详情
hdu5950
题意：t组，输入n,a,b;f(1)=a;f(2)=b;求f(n);f(n)=f(n-1)+2*f(n-2)+n^4;思路：肯定是矩阵快速幂啦，(n+1)^4=n^4+4n^3+6n^2+4n+1,所以为7*7的矩阵，{1,n,n^2,n^3,n^4,f(n),f(n-1)}*A={1,(n+1)^2,(n+2)^3,(n+1)^4,f(n+1),f(n)},1#include<iostre 查看详情
酷派5950手机系统更新后电话薄丢失怎么恢复？
今天，好久没有见面的几个同学突然開始闹腾起来。说是近期工作家庭都不是非常顺，想要出来聚聚，说什么男人的聚会，哎，事实上说白了，不就是几个酒鬼想要出来找酒喝么?只是几年没见。还是有些朋友有点犹豫。 ... 查看详情
msimegb550unify配上5950x可以完全发挥3090显卡的性能吗？
...全发挥其性能吗？参考技术A当然可以完全发挥3090。锐龙5950X的性能足够强了，除非渲染软件，用于游戏都有点性能过剩（目前） 查看详情
hdoj1305
原题链接描述Anencodingofasetofsymbolsissaidtobeimmediatelydecodableifnocodeforonesymbolistheprefixofacodeforanothersymbol.Wewillassumeforthisproblemthatallcodesareinbinary,thatnotwocodeswithinasetofcodesare 查看详情
hdoj3339
原题链接描述Since1945,whenthefirstnuclearbombwasexplodedbytheManhattanProjectteamintheUS,thenumberofnuclearweaponshavesoaredacrosstheglobe.Nowadays,thecrazyboyinFZUnamedAekdyCoinpossessessomenuclearweaponsa 查看详情
hdoj1247
原题链接描述Ahat’swordisawordinthedictionarythatistheconcatenationofexactlytwootherwordsinthedictionary.Youaretofindallthehat’swordsinadictionary.输入Standardinputconsistsofanumberoflowercasewords,oneperline, 查看详情
hdoj1014
ProblemDescriptionComputersimulationsoftenrequirerandomnumbers.Onewaytogeneratepseudo-randomnumbersisviaafunctionoftheformseed(x+1)=[seed(x)+STEP]%MODwhere‘%‘isthemodulusoperator.Suchafunctionwillgene 查看详情