题目链接：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 = n^4 + 4n^3 + 6n^2 + 4n + 1
|1 2 1 4 6 4 1| | f(n+1) | | f(n+2) |
|1 0 0 0 0 0 0| | f(n) | | f(n+1) |
|0 0 1 4 6 4 1| | (n+1)^4 | | (n+2)^4 |
|0 0 0 1 3 3 1| * | (n+1)^3 | = | (n+2)^3 |
|0 0 0 0 1 2 1| | (n+1)^2 | | (n+2)^2 |
|0 0 0 0 0 1 1| | n+1 | | n+2 |
|0 0 0 0 0 0 1| | 1 | | 1 |
#include<cstdio>
using namespace std;
typedef long long ll;
const ll mod = ;
ll n,a,b;
struct Matrix
{
ll m[][];
void init1()
{
m[][] = b,m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ;
m[][] = a,m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ;
m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ;
m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ;
m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ;
m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ;
m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ;
}
void init2()
{
m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ;
m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ;
m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ;
m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ;
m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ;
m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ;
m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ,m[][] = ;
}
Matrix operator * (Matrix t)
{
Matrix res;
for (int i = ; i < ; i++)
{
for (int j = ; j < ; j++)
{
res.m[i][j] = ;
for (int k = ;k < ; k++)
res.m[i][j] = (res.m[i][j] + (m[i][k] % mod) * (t.m[k][j] % mod) % mod) % mod;
}
}
return res;
}
Matrix operator ^ (int k)
{
Matrix res,s;
res.init2();
s.init2();
while(k)
{
if(k & )
res = res * s;
k >>= ;
s = s * s;
}
return res;
}
};
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%lld %lld %lld",&n,&a,&b);
if(n == )
{
printf("%lld\n",a % mod);
continue;
}
if(n == )
{
printf("%lld\n",b % mod);
continue;
}
Matrix ans,t;
ans.init1();
t.init2();
ans = (t^(n-)) * ans;
printf("%lld\n",ans.m[][]);
}
return ;
}