Codeforces Round #265 (Div. 2) E. Substitutes in Number

时间：2022-11-20 15:49:28

http://codeforces.com/contest/465/problem/E

给定一个字符串，以及n个变换操作，将一个数字变成一个字符串，可能为空串，然后最后将字符串当成一个数，取模1e9+7。

逆向操作，维护每次替换后产生的数值和长度

替换P - > d_1d_2……d_n后

新的P的长度Len[ d_1 ] +……+ Len [ d_n ]

新的P值是Val[ d_n ] + 10 ^（Len [ d_n ]）* Val [ d_（n-1）] + 10 ^（Len [ d_n ] + [ d_ len（n-1）]）* Val [ d_（n-2）] +…10 ^（Len [ d_n ] + [ d_ len（n-1）] +……+ Len [ d_2 ]）* Val [ d_1 ]取模。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <stack>

#include <queue>

#include <string>

#include <vector>

#include <set>

#include <map>

#include <cassert>

using namespace std;

#define RD(x) scanf("%d",&x)

#define RD2(x,y) scanf("%d%d",&x,&y)

#define clr0(x) memset(x,0,sizeof(x))

typedef long long LL;

const int maxn = 100005,modo = 1000000007;

char s[maxn],_q[maxn];

int d[maxn];

string q[maxn];

int n,rep[10],pow[10];

int main() {

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

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

        //scanf("%d->%s",&d[i],_q);

        scanf("%s",_q);

        d[i] = _q[0] - '0';

        q[i] = _q+3;

    }

    for(int i = 0;i < 10;++i)

        rep[i] = i,pow[i] = 10;

    for(int i = n-1;i >= 0;--i){

        LL r = 0,p = 1LL;

        for(int j = 0;j < q[i].size();++j){

            int num = q[i][j] - '0';

            p = (p*pow[num])%modo;

            r = (r*pow[num] + rep[num])%modo;

        }

        rep[d[i]] = r;

        pow[d[i]] = p;

    }

    n = strlen(s);

    LL ans = 0;

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

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

        ans = (ans*pow[num]+rep[num])%modo;

    }

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

    return 0;

}

相关文章