「CF464C」Substitutes in Number

2014年9月8日3,9750

Andrew and Eugene are playing a game. Initially, Andrew has string s, consisting of digits. Eugene sends Andrew multiple queries of type “d_i → t_i“, that means “replace all digits d_i in string s with substrings equal to t_i“. For example, if s = 123123, then query “2 → 00” transforms s to 10031003, and query “3 → ” (“replace 3 by an empty string”) transforms it to s = 1212. After all the queries Eugene asks Andrew to find the remainder after division of number with decimal representation equal to s by 1000000007 (10⁹ + 7). When you represent s as a decimal number, please ignore the leading zeroes; also if s is an empty string, then it’s assumed that the number equals to zero.

Andrew got tired of processing Eugene’s requests manually and he asked you to write a program for that. Help him!

Input

The first line contains string s (1 ≤ |s| ≤ 10⁵), consisting of digits — the string before processing all the requests.

The second line contains a single integer n (0 ≤ n ≤ 10⁵) — the number of queries.

The next n lines contain the descriptions of the queries. The i-th query is described by string “d_i->t_i“, where d_i is exactly one digit (from 0 to 9), t_i is a string consisting of digits (t_i can be an empty string). The sum of lengths of t_i for all queries doesn’t exceed 10⁵. The queries are written in the order in which they need to be performed.

Output

Print a single integer — remainder of division of the resulting number by 1000000007 (10⁹ + 7).

Sample test(s)

input

123123
1
2->00

123123

2->00

output

10031003

10031003

input

123123
1
3->

123123

3->

output

1212

1212

input

222
2
2-&gt;0
0-&gt;7

222

2->0

0->7

output

777

777

input

1000000008
0

1 2	1000000008 0

output

1

Note

Note that the leading zeroes are not removed from string s after the replacement (you can see it in the third sample).

题解

简直神题。。。orz无数次jiry_2神的代码才领悟的

题意给定一个数字串，每次把某个数字变成一串数字。。。

最后把数字串当作一个数字，输出其mod1000000007的值

用to[i]表示第i个数字变成的数值（mod），l[i]表示该数字的位数

然后倒序处理这俩个数组，处理过程中使用快速幂

还要注意在变化过程中l[i]可能非常大

这时根据费马小定理，可以取模1000000006

因为a^(p-1) mod p=a^0 mod p

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#define pa pair<int,int>
#define inf 1000000000
#define mod 1000000007
#define ll long long 
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,tot;
char ch[100005],t[100005];
int st[100005],ed[100005],a[100005],b[100005];
int to[10],l[10];
ll qpow(ll a,ll b)
{
	ll ans=1;
	for(ll i=b;i;i>>=1,a=(a*a)%mod)
		if(i&1)ans=(ans*a)%mod;
	return ans;
}
int main()
{
	scanf("%s",ch+1);
	for(int i=0;i<=9;i++)l[i]=1,to[i]=i;
	n=read();
	for(int i=1;i<=n;i++)
	{
		scanf("%s",t+1);
		a[i]=t[1]-'0';
		int len=strlen(t+1);
		if(len==3)st[i]=1;
		else 
		{
			st[i]=tot+1;
			for(int j=4;j<=len;j++)b[++tot]=t[j]-'0';
			ed[i]=tot;
		}
	}
	for(int i=n;i;i--)
	{
		ll t=0,len=0;
		for(int j=st[i];j<=ed[i];j++)
		{
			t=(t*qpow(10,l[b[j]])+to[b[j]])%mod;
			len+=l[b[j]];
			len%=(mod-1);
		}
		l[a[i]]=len;to[a[i]]=t;
	}
	ll ans=0,len=strlen(ch+1);
	for(int i=1;i<=len;i++)ans=(ans*qpow(10,l[ch[i]-'0'])+to[ch[i]-'0'])%mod;
	printf("%I64d",ans);
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<map>

#include<set>

#include<vector>

#include<queue>

#define pa pair<int,int>

#define inf 1000000000

#define mod 1000000007

#define ll long long

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,tot;

char ch[100005],t[100005];

int st[100005],ed[100005],a[100005],b[100005];

int to[10],l[10];

ll qpow(ll a,ll b)

{

ll ans=1;

for(ll i=b;i;i>>=1,a=(a*a)%mod)

if(i&1)ans=(ans*a)%mod;

return ans;

}

int main()

{

scanf("%s",ch+1);

for(int i=0;i<=9;i++)l[i]=1,to[i]=i;

n=read();

for(int i=1;i<=n;i++)

{

scanf("%s",t+1);

a[i]=t[1]-'0';

int len=strlen(t+1);

if(len==3)st[i]=1;

else

{

st[i]=tot+1;

for(int j=4;j<=len;j++)b[++tot]=t[j]-'0';

ed[i]=tot;

}

for(int i=n;i;i--)

{

ll t=0,len=0;

for(int j=st[i];j<=ed[i];j++)

{

t=(t*qpow(10,l[b[j]])+to[b[j]])%mod;

len+=l[b[j]];

len%=(mod-1);

}

l[a[i]]=len;to[a[i]]=t;

}

ll ans=0,len=strlen(ch+1);

for(int i=1;i<=len;i++)ans=(ans*qpow(10,l[ch[i]-'0'])+to[ch[i]-'0'])%mod;

printf("%I64d",ans);

return 0;

}

« 「BZOJ3545」[ONTAK2010] Peaks 「BZOJ1951」[SDOI2010] 古代猪文 »

hzwer.com _ Home | http://hzwer.com

「CF464C」Substitutes in Number

分类目录

热门文章

Myfriends

近期评论