hdu 4382 模拟矩阵连乘高精度 - c++编程基础

题意，有两个容器C1,C2,初始的时候C1中有一个数的值为V，给你K个操作，每次都重复这K个操作N遍，最后问你C2中的数是多少。
N<=10^100。
1：循环操作的次数巨大，敏感的想到这是矩阵连乘的题目。
2：K个操作可以得出一个矩阵，N个K操作就是这个矩阵的N次方
3：最后再乘以初始矩阵即可
构造矩阵也不难，就是if else写个半天，可以看这里
最后需要模拟高精度除法，即一个高精度的数除以一个整数
if else 写的累shi 了
[cpp]
#include
#include
#include
#include
#include
using namespace std;
typedef __int64 lld;
const int mod = 1000000007;
const int maxn = 3;
int n,m;
int V;
int bit[110];
struct Matrix{
lld a[maxn][maxn];
void init0()
{
memset(a,0,sizeof(a));
}
void init1()
{
for(int i=0;i {
for(int j=0;j {
a[i][j]=(i==j);
}
}
}
void print()
{
puts("***************");
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
printf("%I64d ",a[i][j]);
}
puts("");
}
}
};
Matrix matrix_mul(Matrix a,Matrix b)
{
int i,j,k;
Matrix ans;
for(i=0;i {
for(j=0;j {
ans.a[i][j]=0;
for(k=0;k ans.a[i][j]=(ans.a[i][j]+a.a[i][k]*b.a[k][j])%mod;
}
}
return ans;
}
Matrix mult(Matrix a,int b)
{
Matrix ans;
ans.init1();
while(b)
{
if(b&1)

ans=matrix_mul(ans,a);
b>>=1;
a=matrix_mul(a,a);
}
return ans;
}
lld get_val(char *s)
{
lld num=0;
for(int i=0;s[i];i++) num=num*10+s[i]-'0';
return num;
}
int main()
{
int t,ca=1;
scanf("%d",&t);
while(t--)
{
scanf("%d",&V);
char op[10],s1[10],s2[10];
Matrix ms,tmp;
ms.init1();
// ms.print();
while(scanf("%s",op),strcmp(op,"END")!=0)
{
scanf("%s%s",s1,s2);
tmp.init0();
tmp.a[2][2]=1;
if(op[0]=='S')
{
if(s1[1]=='1')
{
if(s2[0]=='C')
{
if(s2[1]=='1') tmp.a[0][0]=tmp.a[1][1]=1;
else tmp.a[1][0]=tmp.a[1][1]=1;
}
else
{
lld num=get_val(s2);
tmp.a[1][1]=1;
tmp.a[2][0]=num;
}
}
else
{
if(s2[0]=='C')
{
if(s2[1]=='1')tmp.a[0][0]=tmp.a[0][1]=1;
else tmp.a[0][0]=tmp.a[1][1]=1;
}
else
{
lld num=get_val(s2);
tmp.a[0][0]=1;
tmp.a[2][1]=num;
}
}
}
else if(op[0]=='A')
{
if(s1[1]=='1')
{
if(s2[0]=='C')
{
if(s2[1]=='1') tmp.a[0][0]=2,tmp.a[1][1]=1;
else tmp.a[0][0]=tmp.a[1][0]=tmp.a[1][1]=1;
}
else
{
lld num=get_val(s2);
tmp.a[0][0]=

hdu 4382 模拟 矩阵连乘 高精度(一)

hdu 4382 模拟矩阵连乘高精度(一)