记录编号	108118	评测结果	AAAAA
题目名称	[NOIP 2002]产生数	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2014-07-02 11:57:36	内存使用	0.29 MiB

#include <cstdio>
#include <cstring>
 
using namespace std;
 
/*******************bign*************************/
 
struct bign{
	int len;
	int num[15];
};
 
inline bign bign_init(int a)
{
	bign temp={0};
	while(a)
	{
		temp.num[temp.len++]=a%10000;
		a/=10000;
	}
	return temp;
}
 
inline void bign_print(bign a)
{
	if(a.len==0)
	{
		printf("0");
		return;
	}
	printf("%d",a.num[a.len-1]);
	for(int i=a.len-2;i>=0;i--)
	{
		printf("%04d",a.num[i]);
	}
}
 
inline bign bign_tim(bign a,bign b)
{
	bign temp={0};
	
	temp.len=a.len+b.len-1;
	
	for(int i=0;i<a.len;i++)
	{
		for(int j=0;j<b.len;j++)
		{
			temp.num[i+j]+=a.num[i]*b.num[j];
		}
	}
	
	for(int i=0;i<temp.len;i++)
	{
		if (temp.num[i]>10000)
		{
			temp.num[i+1]+=temp.num[i]/10000;
			temp.num[i]%=10000;
		}
	}
	
	if(temp.num[temp.len]!=0)
	{
		temp.len++;
	}
	
	return temp;
}
 
/******************bign************************/
 
char s[51];
int m,x,y;
bool V[11][11]={0};
 
void init(void)
{
	scanf("%s %d\n",s,&m);
	
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d",&x,&y);
		V[x][y]=true;
	}
	
	for(int i=0;i<=9;i++)
	{
		V[i][i]=true;
	}
}
 
void floyed(void)
{
	for(int k=0;k<=9;k++)
	{
		for(int i=0;i<=9;i++)
		{
			for(int j=0;j<=9;j++)
			{
				if(i!=j&&j!=k&&k!=i)
				{
					V[i][j]=V[i][j]||(V[i][k]&&V[k][j]);
				}
			}
		}
	}
}
 
void work(void)
{
	bign total=bign_init(1);
	
	for(int i=0;i<strlen(s);i++)
	{
		int ans=0,tmp=s[i]-'0';
		
		for(int j=0;j<=9;j++)
		{
			if(V[tmp][j])
			{
				ans++;
			}
		}
		
		total=bign_tim(total,bign_init(ans));
	}
	
	bign_print(total);
}
 
int main()
{
	freopen("build.in","r",stdin);
	freopen("build.out","w",stdout);
	
	init();
	floyed();
	work();
	
	return 0;
}