Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstring>
- #include <algorithm>
- using namespace std;
- typedef long long ll;
- const ll mod = 1e9+7;
- const ll inverz10 = 700000005;
- const int MAXN=3001;
- string s1,s2;
- ll nep[3002],par[3002];
- ll dp[3002];
- ll komb[3002],sumkomb[3002];
- ll dp3[3002];
- int niz[3002];
- int i,b,g,n;
- void prepro(){
- nep[0]=par[0]=1;
- nep[1]=10;
- for(i=3;i<=MAXN;i+=2)nep[i]=nep[i-2]*10%mod;
- par[2]=10;
- for(i=4;i<=MAXN;i+=2)par[i]=par[i-2]*10%mod;
- komb[0]=1;
- komb[1]=10;
- int dul;
- for(i=2;i<=MAXN;i++){
- for(b=i-1;b>=0;b--){
- dul=i-b;
- if( dul&1 )komb[i]+=komb[b]*nep[dul];
- else komb[i]+=komb[b]*par[dul];
- komb[i]%=mod;
- }
- }
- for(i=1;i<MAXN;i++)sumkomb[i]=( sumkomb[i-1] + 9*inverz10%mod*komb[i] ) % mod;
- for(i=1;i<=MAXN;i++)
- for(b=1;b<=i;b++){
- if( b&1 )dp3[i] = ( dp3[i] + nep[b]*komb[i-b] ) % mod;
- else dp3[i] = ( dp3[i] + par[b]*komb[i-b] ) % mod;
- }
- }
- bool moze[3002][3002];
- void racunaj(int n){
- for(i=1;i<=n;i++){
- for(b=0;0<i-b && i+b<=n;b++){
- if( niz[i-b] != niz[i+b] )break;
- moze[i-b][i+b]=true;
- }
- }
- for(i=1;i<=n;i++){
- int pr=i,dr=i+1;
- for(;0<pr && dr<=n;pr--,dr++){
- if( niz[pr]!=niz[dr] )break;
- moze[pr][dr]=true;
- }
- }
- }
- ll dajga(string s){
- if(s=="0")return 0;
- n=s.size();
- for(i=1;i<=n;i++)niz[i]=s[i-1]-'0';
- ll ret=sumkomb[n-1];
- moze[0][0]=1;
- memset(moze,0,sizeof moze) , memset( dp , 0 , sizeof dp );
- racunaj(n);
- dp[0]=1;
- for(i=1;i<=n;i++){
- for(b=i-1;b>=0;b--){
- dp[i]+=dp[b]*moze[b+1][i];
- dp[i]%=mod;
- }
- }
- ret= ( ret + inverz10*(niz[1]-1)%mod*komb[n] ) % mod;
- for(i=1;i<n;i++){
- ret+=dp[i]*inverz10%mod*niz[i+1]%mod*komb[n-i];
- ret%=mod;
- }
- ret+=dp[n];
- for(i=1;i<=n;i++){ // lijevi rub
- int pr=1,dr=i;
- ll sum=0;
- while( pr<dr ){
- sum+=dp[pr-1]*komb[n-dr];
- sum%=mod;
- if( moze[pr+1][dr-1] && niz[pr]<niz[dr] )
- ret=(ret+sum)%mod;
- pr++,dr--;
- }
- }
- for(i=2;i<n;i++){// desni rub
- int pr=i,dr=n;
- ll sum=0;
- while( pr<dr ){
- sum+=dp[pr-1]*komb[n-dr];
- sum%=mod;
- if( moze[pr+1][dr-1] && niz[pr]<niz[dr] )
- ret=(ret+sum)%mod;
- pr++,dr--;
- }
- }
- for(i=1;i<n;i++){//odgovor je znan
- for(b=1;i-b>=0 && i+b<=n;b++){
- if( niz[i] < niz[i+1] )ret=(ret+dp[i-b]*komb[n-(i+b)]%mod)%mod;
- ret+=dp[i-b]*inverz10%mod*dp3[n-(i+b)]%mod*niz[i+1];
- ret%=mod;
- }
- }
- return ret;
- }
- void smanji( string &s ){
- int sz=s.size();
- for(i=sz-1;i>=0;i--){
- s[i]--;
- if( s[i]<'0' )s[i]='9';
- else break;
- }
- if(s[0]=='0'){
- reverse(s.begin(),s.end());
- s.pop_back();
- reverse(s.begin(),s.end());
- }
- }
- int main(){
- cin>>s1;
- cin>>s2;
- smanji(s1);
- prepro();
- // while(1){
- // string es;
- // cin>>es;
- // dajga(es);
- // }
- cout<< ( mod + dajga( s2 ) - dajga( s1 ) ) % mod <<endl;
- return 0;
- }
- /*
- 100
- 101
- 5069
- 133506
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement