codeforces #464C Substitutes in Number - c++编程基础

题目大意：给定一个 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<