2015
05-24

# Harry Potter and Cyber Sequence Generator

After Voldemort and the Death Eater were wiped out by Harry Potter and his friends, Harry becomes the glory of the Wizarding World, magician treat him as model, hero, king… and much more than that.
Recently Harry Potter and his friends have been researching a kind of toy from the Muggle World, with the name Cyber Sequence Generator, wondering if after manipulated in some certain way, it can be useful and powerful for magicians.
This kind of generator has two magic containers C1 and C2, if we put a magic element in C1, after its magic is all over, the result magic element can be taken from C2. Because we Muggles(I’m sorry if you are not a muggle, you can ask me for magic student version of this problem statement even you are competing and can’t use the Internet) do not know magic languages, let’s rearrange the words to describe how the generator works.
The generator’s work can be split into simple works. Each work is like:
     SET|ADD    C1|C2,    C1|C2|IntegerNumber     MUL        C1|C2,    IntegerNumber

By “SET a,b “, we have the value of the element in container a changed to b
By “ADD a,b “, we have the value of the element in container a added by b
By “MUL a,b “, we have the value of the element in container a multiplied by b
After each of the operations, the value in b will not change.
Here C1, C2 denotes actually the value of magic element.
C2’s initial value is 0.
All works are done in the order in input.

Harry always has a magic element V at first, and can use the generator arbitary times, and wonders if so, what is the value of the result element.

One line T, the number of test cases.
For each test case, first line contains one integer V. Then a few lines describe the Cyber Sequence Generator, ended by “END”.
Then an integer Q, the number of Queries.
Q number following describe how many times Harry use the generator, for each query N , we have the initial value is V, and C2’s initial value is 0.
The instruction is like "SET_a,_b".(underscore ‘_’ is just used to demonstrate blank char)

One line T, the number of test cases.
For each test case, first line contains one integer V. Then a few lines describe the Cyber Sequence Generator, ended by “END”.
Then an integer Q, the number of Queries.
Q number following describe how many times Harry use the generator, for each query N , we have the initial value is V, and C2’s initial value is 0.
The instruction is like "SET_a,_b".(underscore ‘_’ is just used to demonstrate blank char)

2
1
SET C2, C1
END
5
1
2
3
4
5
1
SET C2, 1
SET C1, C2
END
5
1
2
3
4
5

Case 1:
2
3
4
5
6
Case 2:
3
7
15
31
63

N<=10^100。

1：循环操作的次数巨大，敏感的想到这是矩阵连乘的题目。

2：K个操作可以得出一个矩阵，N个K操作就是这个矩阵的N次方

3：最后再乘以初始矩阵即可

if else 写的累shi 了

#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;
}