Advertisement
Guest User

Untitled

a guest
Mar 21st, 2018
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.92 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. using namespace std;
  5. typedef long long ll;
  6. const ll mod = 1e9+7;
  7. const ll inverz10 = 700000005;
  8. const int MAXN=3001;
  9. string s1,s2;
  10.  
  11. ll nep[3002],par[3002];
  12. ll dp[3002];
  13. ll komb[3002],sumkomb[3002];
  14. ll dp3[3002];
  15. int niz[3002];
  16. int i,b,g,n;
  17.  
  18. void prepro(){
  19.    
  20.     nep[0]=par[0]=1;
  21.     nep[1]=10;
  22.     for(i=3;i<=MAXN;i+=2)nep[i]=nep[i-2]*10%mod;
  23.    
  24.     par[2]=10;
  25.     for(i=4;i<=MAXN;i+=2)par[i]=par[i-2]*10%mod;
  26.    
  27.     komb[0]=1;
  28.     komb[1]=10;
  29.    
  30.     int dul;
  31.    
  32.     for(i=2;i<=MAXN;i++){
  33.         for(b=i-1;b>=0;b--){
  34.             dul=i-b;
  35.             if( dul&1 )komb[i]+=komb[b]*nep[dul];
  36.             else komb[i]+=komb[b]*par[dul];
  37.             komb[i]%=mod;
  38.         }
  39.     }
  40.    
  41.     for(i=1;i<MAXN;i++)sumkomb[i]=( sumkomb[i-1] + 9*inverz10%mod*komb[i] ) % mod;
  42.    
  43.     for(i=1;i<=MAXN;i++)
  44.         for(b=1;b<=i;b++){
  45.             if( b&1 )dp3[i] = ( dp3[i] + nep[b]*komb[i-b] ) % mod;
  46.             else dp3[i] = ( dp3[i] + par[b]*komb[i-b] ) % mod;
  47.         }
  48.        
  49. }
  50.  
  51. bool moze[3002][3002];
  52.  
  53. void racunaj(int n){
  54.    
  55.     for(i=1;i<=n;i++){
  56.         for(b=0;0<i-b && i+b<=n;b++){
  57.             if( niz[i-b] != niz[i+b] )break;
  58.             moze[i-b][i+b]=true;
  59.         }
  60.     }
  61.    
  62.     for(i=1;i<=n;i++){
  63.         int pr=i,dr=i+1;
  64.         for(;0<pr && dr<=n;pr--,dr++){
  65.             if( niz[pr]!=niz[dr] )break;
  66.             moze[pr][dr]=true;
  67.         }
  68.     }
  69.    
  70. }
  71.  
  72. ll dajga(string s){
  73.     if(s=="0")return 0;
  74.     n=s.size();
  75.     for(i=1;i<=n;i++)niz[i]=s[i-1]-'0';
  76.    
  77.     ll ret=sumkomb[n-1];
  78.    
  79.     moze[0][0]=1;
  80.     memset(moze,0,sizeof moze) , memset( dp , 0 , sizeof dp );
  81.    
  82.     racunaj(n);
  83.    
  84.     dp[0]=1;
  85.     for(i=1;i<=n;i++){
  86.         for(b=i-1;b>=0;b--){
  87.             dp[i]+=dp[b]*moze[b+1][i];
  88.             dp[i]%=mod;
  89.         }
  90.     }
  91.    
  92.     ret= ( ret + inverz10*(niz[1]-1)%mod*komb[n] ) % mod;
  93.     for(i=1;i<n;i++){
  94.         ret+=dp[i]*inverz10%mod*niz[i+1]%mod*komb[n-i];
  95.         ret%=mod;
  96.     }
  97.    
  98.     ret+=dp[n];
  99.    
  100.     for(i=1;i<=n;i++){ // lijevi rub
  101.         int pr=1,dr=i;
  102.         ll sum=0;
  103.         while( pr<dr ){
  104.             sum+=dp[pr-1]*komb[n-dr];
  105.             sum%=mod;
  106.            
  107.             if( moze[pr+1][dr-1]  && niz[pr]<niz[dr] )
  108.                 ret=(ret+sum)%mod;
  109.            
  110.             pr++,dr--;
  111.         }
  112.     }
  113.    
  114.     for(i=2;i<n;i++){// desni rub
  115.         int pr=i,dr=n;
  116.         ll sum=0;
  117.         while( pr<dr ){
  118.             sum+=dp[pr-1]*komb[n-dr];
  119.             sum%=mod;
  120.            
  121.             if( moze[pr+1][dr-1] && niz[pr]<niz[dr] )
  122.                 ret=(ret+sum)%mod;
  123.            
  124.             pr++,dr--;
  125.         }
  126.     }
  127.    
  128.     for(i=1;i<n;i++){//odgovor je znan
  129.    
  130.         for(b=1;i-b>=0 && i+b<=n;b++){
  131.             if( niz[i] < niz[i+1] )ret=(ret+dp[i-b]*komb[n-(i+b)]%mod)%mod;
  132.            
  133.             ret+=dp[i-b]*inverz10%mod*dp3[n-(i+b)]%mod*niz[i+1];
  134.             ret%=mod;
  135.         }
  136.     }
  137.    
  138.     return ret;
  139. }
  140.  
  141. void smanji( string &s ){
  142.     int sz=s.size();
  143.     for(i=sz-1;i>=0;i--){
  144.         s[i]--;
  145.         if( s[i]<'0' )s[i]='9';
  146.         else break;
  147.     }
  148.     if(s[0]=='0'){
  149.         reverse(s.begin(),s.end());
  150.         s.pop_back();
  151.         reverse(s.begin(),s.end());
  152.     }
  153.    
  154. }
  155.  
  156. int main(){
  157.  
  158.     cin>>s1;
  159.     cin>>s2;
  160.    
  161.     smanji(s1);
  162.    
  163.     prepro();
  164.    
  165. //  while(1){
  166. //      string es;
  167. //      cin>>es;
  168. //      dajga(es);
  169. //  }
  170.    
  171.     cout<< ( mod + dajga( s2 ) - dajga( s1 ) ) % mod <<endl;
  172.    
  173.     return 0;
  174. }
  175.  
  176. /*
  177.  
  178. 100
  179. 101
  180.  
  181. 5069
  182. 133506
  183.  
  184. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement