首页 > ACM题库 > HDU-杭电 > HDU 4382-Harry Potter and Cyber Sequence Generator-模拟-[解题报告]HOJ
2015
05-24

HDU 4382-Harry Potter and Cyber Sequence Generator-模拟-[解题报告]HOJ

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
ADD C1, 1
SET C2, C1
END
5
1
2
3
4
5
1
ADD C1, C1
SET C2, 1
ADD C2, C1
SET C1, C2
END
5
1
2
3
4
5

样例输出:

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

链接:http://acm.hdu.edu.cn/showproblem.php?pid=4382

题意,有两个容器C1,C2,初始的时候C1中有一个数的值为V,给你K个操作,每次都重复这K个操作N遍,最后问你C2中的数是多少。

N<=10^100。

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

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

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

构造矩阵也不难,就是if else写个半天,可以看这里

最后需要模拟高精度除法,即一个高精度的数除以一个整数

if else 写的累shi 了Harry Potter and Cyber Sequence Generator

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

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/crazy_ac/article/details/7895723