[CF 464C] Substitutes in Number

作法：

對於一連串的替換操作，可以發現到其實「$1$」這個字不管是落在原字串的哪裡，最後一定都會變成一個固定的很長的字串，這對於$0,...,9$都成立。因此如果我們能算出每個字元在經過所有的替換之後變成的字串的長度，和這個字串本身模$10^9+7$的值，就可以$O(n)$算出答案了。具體來說，假設原字串是$123456$，並且一連串的操作把$6$變成了$777$，$5$變成了$888$，$4$變成了$999$，那麼我們可以算出原本的$4$變成$999$之後應該要乘上$10$的幾次才會是他實際上的值，不難發現他其實就是「$5$最後的字串長度$+6$最後的字串長度」，所以就得到了$999\cdot 10^6$。只要這樣算出每個字元的答案的總和就可以了。

至於如何求最後字串長度和模$10^9+7$的值（以下稱其為$len$值和$val$值），可以把整個過程倒過來看。當沒有進行任何替換時，$0~9$的長度都是$1$，$val$值則是他本身。再來觀察只有進行最後一次替換時$0~9$的$len$值和$val$值應該會是多少，假設這次替換是$x->S$，那麼可以發現此時$len[x]=S$的長度，$val[x]$則變成了$S$代表的值，其他數的$len,val$則不變。

再來我們的目的是，假設現在已經有了「考慮第$i$個替換到最後一個替換時，每個數的$len$和$val$值」，想要推到「考慮第$i-1$個到最後一個時」的兩種值，而這很容易從上面觀察出一般的情形，可以發現其實新的$len[x]$值就是由舊的$len$陣列中，把$S$的每一個字元代入再加起來的結果，而$val[x]$則比較複雜，不過基本上和前面所講的「$O(n)$算出原數列的答案」的精神類似，因為我們知道$S$中的每個字元在經過了第$i$次到最後一次替換之後會變成什麼值了，所以就可以求出$S$經過了第$i$次到最後一次替換後會變成多少，而這個值就是新的$val[x]$了。

最後要注意到，$len$值會爆 long long，事實上我們可以把$len$值拿去模$10^9+7-1$，因為其實可以發現$len$值就是被用來放在$10$的冪次，以求得一個字元真正代表的值的，而因為$10^9+7$是一個質數（記為$p$），由費馬小定理知$a^{p-1}\equiv 1(mod p)$，因此把$len$值加減$p-1$並不會影響結果，所以模$p-1$才會是對的。

code :

#include<bits/stdc++.h>
#define LL long long
#define MOD 1000000007
using namespace std;
const int maxn=100000+10 ;
 
LL pow(LL x,LL n,int mod)
{
    if(n<=1) return n ? x : 1LL ;
    LL t=pow(x,n/2,mod) ;
    if(n&1) return (t*t%mod)*x%mod ;
    else return t*t%mod ;
}
LL pw[maxn] ;
 
char s[maxn],t[maxn] ;
int n,d[maxn] ;
string st[maxn] ;
LL len[maxn],val[maxn] ;
main()
{
    pw[0]=1 ;
    for(int i=1;i<maxn;i++) pw[i]=pw[i-1]*10%MOD ;
    scanf("%s%d",s,&n) ;
    for(int i=1;i<=n;i++)
    {
        scanf("%s",t) ;
        d[i]=t[0]-'0' ;
        st[i]=string(t+3,t+strlen(t)) ;
    }
    for(int i=0;i<10;i++) len[i]=1 , val[i]=i ;
    for(int i=n;i>=1;i--)
    {
        int sz=st[i].size() ;
        LL l2=0LL , val2=0LL ;
        for(int j=sz-1;j>=0;j--)
        {
            val2=(val2+val[st[i][j]-'0']*pow(10,l2,MOD))%MOD ;
            l2=(l2+len[st[i][j]-'0'])%(MOD-1) ;
        }
        len[d[i]]=l2 , val[d[i]]=val2 ;
    }
    LL ans=0LL ;
    for(int i=strlen(s)-1,nowl=0;i>=0;i--)
    {
        ans+=val[s[i]-'0']*pow(10,nowl,MOD) ;
        ans%=MOD ;
        nowl=(nowl+len[s[i]-'0'])%(MOD-1) ;
    }
    printf("%I64d\n",ans) ;
}