HDU 6470 Counting(矩阵快速幂)
先BB几句:
1.可以顺着链接摸到大佬这题的题解,看他的题解也可以。(既然来了就留下好吗)
2.然后矩阵快速幂这个东西呢,感觉就是为了处理那种数组开不起,多组暴力会超时的递推式的题目。
解题思路:
1. 了解快速幂 https://blog.csdn.net/weixin_43272781/article/details/85058595
举个例子:a^b,假设b=11,转化为2进制1011
一步步来,二进制最后一位是1,ans = ans*a;(ans初值为1)
倒数第二位是1,ans = ans*(a^2)
倒数第三位是0,ans不操作 (如果是1,就ans = ans*a^4)
第一位是1,ans = ans*(a^8)
2. 了解矩阵乘法(应该都会)
3. 了解怎么根据递推式推出初始矩阵,转移矩阵https://blog.csdn.net/weixin_43272781/article/details/88878064
这一步应该最为关键。
4. 了解矩阵快速幂 https://blog.csdn.net/weixin_43272781/article/details/85939539
5. 这题的矩阵是这样的(不止一种写法)
不知道哪个写字这么丑的敢把图传上来
代码:
#include<cstdio>
#include<cstring>
#define mod 123456789
typedef long long ll;
void mulmatrix(ll a[][6],ll b[][6])
{
ll temp[6][6]={0};
for (int i=0;i<6;i++)
for (int j=0;j<6;j++)
for (int k=0;k<6;k++)
temp[i][j] = (temp[i][j] + a[i][k]*b[k][j])%mod;
for (int i=0;i<6;i++)
for (int j=0;j<6;j++)
a[i][j] = temp[i][j];
}
void fast_power(ll a[][6],ll n)
{
ll ans[6][6]={0};
for (int i=0;i<6;i++) ans[i][i] = 1;
while (n){
if (n&1) mulmatrix(ans,a);
n>>=1;
mulmatrix(a,a);
}
for (int i=0;i<6;i++)
for (int j=0;j<6;j++)
a[i][j] = ans[i][j];
}
int main()
{
ll n,t;
scanf("%lld",&t);
while (t--){
scanf("%lld",&n);
ll init[][6]={{2,1,27,27,9,1},
{0,0,0,0,0,0},
{0,0,0,0,0,0},
{0,0,0,0,0,0},
{0,0,0,0,0,0},
{0,0,0,0,0,0}};
ll trans[][6]={{1,1,0,0,0,0},
{2,0,0,0,0,0},
{1,0,1,0,0,0},
{0,0,1,1,0,0},
{0,0,1,2,1,0},
{0,0,1,3,3,1}};
if (n==1) printf("1\n");
else if (n==2) printf("2\n");
else {
fast_power(trans,n-2);
mulmatrix(init,trans);
printf("%lld\n",init[0][0]%mod);
}
}
return 0;
}