題意，有兩個容器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<cstdio>
#include<cstring>
#include<vector>
#include<map>
#include<algorithm>
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<maxn;i++)
{
for(int j=0;j<maxn;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<maxn;i++)
{
for(j=0;j<maxn;j++)
{
ans.a[i][j]=0;
for(k=0;k<maxn;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]=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]=tmp.a[1][1]=1;
else tmp.a[0][0]=1,tmp.a[1][1]=2;
}
else
{
lld num=get_val(s2);
tmp.a[0][0]=tmp.a[1][1]=1;
tmp.a[2][1]=num;
}
}
}
else
{
lld num=get_val(s2);
if(s1[1]=='1')
{
tmp.a[0][0]=num;
tmp.a[1][1]=1;
}
else
{
tmp.a[0][0]=1;
tmp.a[1][1]=num;
}
}
//tmp.print();
// ms.print();
ms=matrix_mul(ms,tmp);
// ms.print();
}
Matrix mat=ms;
int Q;
char num[110];
scanf("%d",&Q);
printf("Case %d:\n",ca++);
while(Q--)
{
ms.init0();
ms.a[0][0]=V,ms.a[0][2]=1;
tmp=mat;
scanf("%s",num);
int len=strlen(num);
for(int i=0;i<len;i++) bit[i]=num[len-1-i]-'0';
while(len>0)
{
if(bit[0]&1) ms=matrix_mul(ms,tmp);
tmp=matrix_mul(tmp,tmp);
int pre=0,sum;
for(int i=len-1;i>=0;i--)
{
sum=bit[i]+pre*10;
bit[i]= (sum>>1);
pre=sum&1;
}
while(len>0 && bit[len-1]==0) len--;
}
printf("%I64d\n",ms.a[0][1]);
}
}
return 0;
}
