codeforces #464C Substitutes in Number

codeforces #464C Substitutes in Number

題目大意：給定一個105位的數字，每次操作選擇一個數字x(0≤x≤9)，將所有的x替換成數字串s，求最終的結果 mod 109+7
由於最終數字的長度是指數級別的，我們不能模擬
考慮倒著做
fi,j表示執行[i,n]中的所有操作後數字j(0≤j≤9)會變成什麼
當然這個數字可能非常大，因此我們只需要儲存變換後的數值對109+7的模數以及變換後的位數對109+6的模數就行了
然後……隨便搞一搞就好了

#include 
#include 
#include 
#include 
#define M 100100
#define MOD 1000000007
using namespace std;
int n;
pair f[M][10];
int a[M];
char s[M],mempool[M<<1],*C=mempool,*st[M];
long long Quick_Power(long long x,int y)
{
    long long re=1;
    while(y)
    {
        if(y&1) (re*=x)%=MOD;
        (x*=x)%=MOD; y>>=1;
    }
    return re;
}
pair Calculate(char s[],pair table[10])
{
    pair re(0,0);
    int i;
    for(i=0;s[i];i++);
    for(i--;~i;i--)
    {
        (re.first+=Quick_Power(10,re.second)*table[s[i]-'0'].first%MOD)%=MOD;
        (re.second+=table[s[i]-'0'].second)%=(MOD-1);
    }
    return re;
}
int main()
{
    static char buffer[M];
    int i,j;
    scanf("%s",s);
    cin>>n;
    for(i=1;i<=n;i++)
    {
        scanf("%s",buffer);
        a[i]=buffer[0]-'0';
        strcpy(C,buffer+3);
        st[i]=C;while(*C++);
    }
    for(i=0;i<10;i++)
        f[n+1][i]=make_pair(i,1);
    for(i=n;i;i--)
    {
        for(j=0;j<10;j++)
            if(a[i]!=j)
                f[i][j]=f[i+1][j];
            else
                f[i][j]=Calculate(st[i],f[i+1]);
    }
    cout<