2016ACM/ICPC亚洲区沈阳站（区域赛练习）（C 矩阵快速幂）
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int a,b;
cin>>a>>b;
cout<<2*max(a,b)+min(a,b)<<endl;
}
return 0;
}#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
char ss[15];
cin>>n;
getchar();
while(n--)
{
cin>>ss;
int len=strlen(ss);
int cnth=0;
int cntc=0;
int cnto=0;
int sum=0;
for(int i=0;i<len;i++)
{
if(ss[i]=='H')
cnth++;
else if(ss[i]=='C')
cntc++;
if(ss[i]=='O')
cnto++;
}
sum=cnth*1+cntc*12+cnto*16;
cout<<sum<<endl;
}
return 0;
}知识点：矩阵快速幂
1.根据题目描述，我们可以分析出：F(n) = F(n-1) + 2F(n-2) + n^4 并且F(1) = a , F(2) = b，求F(n)%2147493647，其中a、b、n是待输入的参数。
2.才刚开始接触矩阵快速幂，首先去学习什么是矩阵快速幂？
2.1矩阵快速幂介绍：
矩阵的快速幂运算，其实思路和整数快速幂是一样的。比如求矩阵A^7，本来是要求8次，我们先求出A^2，然后以A^2为基 础，这样求4次即可.（矩阵快速幂之所以称之为矩阵快速幂，说白了就是对矩阵进行快速幂的运算）
2.2 矩阵快速幂求解步骤：
2.2.1. 把非线性递推式转化为线性递推式
2.2.2. 根据线性递推式得到F(n)和F(n+1)的矩阵序列
2.2.3. 根据F(n)和F(n+1)的矩阵序列得到中间的转移矩阵
2.2.4. 根据转移矩阵编写代码
3.针对本来来说：
3.1把非线性递推式转化为线性递推式：
F(n+1) = F(n) + 2F(n-1) + n^4 + 4n^3 + 6n^2 + 4n + n^0
3.2根据线性递推式得到F(n)和F(n+1)的矩阵序列
补充一下矩阵相乘的原则：只有当A矩阵的行数等于B矩阵的列数的时候，才可以做乘法运算。并且：A（的列）*B（的行）
3.3 根据F(n)和F(n+1)的矩阵序列得到中间的转移矩阵
有了第二步的基础，那么我们现在就可以来推算转移矩阵[A]了，所求转移矩阵为：
long long num[7][7] = {1, 2, 1, 4, 6, 4, 1,
1, 0, 0, 0, 0, 0, 0,
0, 0, 1, 4, 6, 4, 1,
0, 0, 0, 1, 3, 3, 1,
0, 0, 0, 0, 1, 2, 1,
0, 0, 0, 0, 0, 1, 1,
0, 0, 0, 0, 0, 0, 1};f1=a;f2=b;f3= 2a + b + 2^4 + 4×2^3 + 6×2^2 + 4×2^1 + 2^0;
最后可以发现：B2 × An-2 = Bn（fn）（时间仓促，未整理完，日后待补。。。。）
#include<bits/stdc++.h>
using namespace std;
#define mod 2147493647
int t;
int N,a,b;
void init(long long num[][7])
{
for(int i=0;i<7;i++)
{
for(int j=0;j<7;j++)
{
if(i==j)
num[i][j]=1;
else num[i][j]=0;
}
}
}
void cheng(long long (&aa)[7][7], long long bb[7][7])
{
long long ans[7][7]={0};
for(int i=0;i<7;i++)
{
for(int j=0;j<7;j++)
{
for(int k=0;k<7;k++)
{
ans[i][j]=(ans[i][j]+aa[i][k]*bb[k][j])%mod;
}
}
}
for(int i=0;i<7;i++)
{
for(int j=0;j<7;j++)
{
aa[i][j]=ans[i][j];
}
}
}
int main()
{
long long center[7][7];//单位矩阵
cin>>t;
while(t--)
{
scanf("%d%d%d",&N,&a,&b);
if(N==1)
{
cout<<a<<endl;
continue;
}
long long num[7][7] = {1, 2, 1, 4, 6, 4, 1,
1, 0, 0, 0, 0, 0, 0,
0, 0, 1, 4, 6, 4, 1,
0, 0, 0, 1, 3, 3, 1,
0, 0, 0, 0, 1, 2, 1,
0, 0, 0, 0, 0, 1, 1,
0, 0, 0, 0, 0, 0, 1};
init(center);
N=N-2;
while(N)
{
if(N&1) cheng(center,num);
cheng(num,num);
N=N/2;
}
long long int sum=0;
sum=(sum+b*center[0][0])%mod;
sum=(sum+a*center[0][1])%mod;
sum=(sum+16*center[0][2])%mod;
sum=(sum+8*center[0][3])%mod;
sum=(sum+4*center[0][4])%mod;
sum=(sum+2*center[0][5])%mod;
sum=(sum+center[0][6])%mod;
printf("%d\n",sum);
}
return 0;
}