CF464C-Substitutes in Number

题意

开始给出一个长为\(n\)的数字串，有\(m\)次操作按顺序执行，每次把当前数字串中的某一个数码替换成一个数字串\(t\)（可以为空或多位），最后问操作结束后的数字串十进制下模\(10^9+7\)的值。

\(n,m,\sum t\le 10^5\)。

分析

这题很妙啊！

直接做肯定是不行的，因为替换的时候长度没有保证。遇到这种前面对后面有影响的问题，可以考虑反过来做。

如果能够求出所有操作结束后，每个数码代表什么数字串，那么直接代入开始的串就可以得到答案了！

对于每一种数码（0-9）保存到现在为止它代表的数字串模\(10^9+7\)的值，以及它的长度（可以直接用\(10^k\)来表示）。从后往前操作，每一次会改动一种数码，就把改后串用当前的数码状态计算一个当前值出来，代表这个数码当前代表了什么值。

其实就是一个从后往前计算回代的过程。这种from the other end的思路是很奇妙的。

代码

#include<cstdio>

#include<cstring>

#include<string>

#include<utility>

#include<algorithm>

using namespace std;

typedef long long giant;

const int maxn=1e5+10;

const int q=1e9+7;

inline int Plus(int x,int y) {return ((giant)x+(giant)y)%q;}

inline int Multi(int x,int y) {return (giant)x*y%q;}

char s[maxn];

pair<int,string> c[maxn];

pair<int,int> a[10],b[10];

int main() {

#ifndef ONLINE_JUDGE

	freopen("test.in","r",stdin);

#endif

	int n;

	scanf("%s%d",s+1,&n);

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

		static char t[maxn];

		int d;

		scanf("%s",t);

		c[i]=make_pair(t[0]-'0',t+3);

	}

	for (int i=0;i<10;++i) a[i]=make_pair(i,10);

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

		int len=c[i].second.length(),d=c[i].first;

		int &shu=b[d].first=0,&tmp=b[d].second=1;

		if (!len) {

			a[d]=b[d];

			continue;

		}

		for (int j=len-1;j>=0;--j) {

			int x=c[i].second[j]-'0';

			shu=Plus(shu,Multi(tmp,a[x].first));

			tmp=Multi(tmp,a[x].second);

		}

		a[d]=b[d];

	}

	int m=strlen(s+1),ans=0;

	for (int i=m,tmp=1;i;--i) {

		int x=s[i]-'0';

		ans=Plus(ans,Multi(tmp,a[x].first));

		tmp=Multi(tmp,a[x].second);

	}

	printf("%d\n",ans);

	return 0;

}