Submission #74772606

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define fi first
#define se second
#define ckadd(x,y) x=(x+y)%mod

namespace io{const int __SIZE=(1<<21)+1;char ibuf[__SIZE],*iS,*iT,obuf[__SIZE],*oS=obuf,*oT=oS+__SIZE-1,__c,qu[55];int __f,qr,_eof;
#define Gc()(iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,__SIZE,stdin),(iS==iT?EOF:*iS++)):*iS++)
	inline void flush(){fwrite(obuf,1,oS-obuf,stdout),oS=obuf;}inline void gc(char&x){x=Gc();}inline void pc(char x){*oS++=x;if(oS==oT)flush();}inline void pstr(const char*s){int __len=strlen(s);for(__f=0;__f<__len;++__f)pc(s[__f]);}inline void gstr(char*s){for(__c=Gc();__c<32||__c>126||__c==' ';)__c=Gc();for(;__c>31&&__c<127&&__c!=' '&&__c!='\n'&&__c!='\r';++s,__c=Gc())*s=__c;*s=0;}template<class I>inline bool gi(I&x){_eof=0;for(__f=1,__c=Gc();(__c<'0'||__c>'9')&&!_eof;__c=Gc()){if(__c=='-')__f=-1;_eof|=__c==EOF;}for(x=0;__c<='9'&&__c>='0'&&!_eof;__c=Gc())x=x*10+(__c&15),_eof|=__c==EOF;x*=__f;return!_eof;}template<class I>inline void print(I x){if(!x)pc('0');if(x<0)pc('-'),x=-x;while(x)qu[++qr]=x%10+'0',x/=10;while(qr)pc(qu[qr--]);}struct Flusher_{~Flusher_(){flush();}}io_flusher_;}using io::pc;using io::gc;using io::pstr;using io::gstr;using io::gi;using io::print;

constexpr int mod=1e9+7;
string s;
int n;

pair<ll,ll> f[30][10][2];

pair<ll,ll> dfs(int x,int lst,int has0,int limt,int lead){
	if(x==n){
		if(lead) return {0,0};
		if(has0) return {0,2};
		return {0,1};
	}
	if(!limt&&!lead&&f[x][lst][has0].fi!=-1)
		return f[x][lst][has0];
	int up=(limt?s[x]-'0':9);
	pair<ll,ll> res={0,0};
	for(int i=0;i<=up;i++){
		int nlimt=limt&&(i==up);
		int nlead=lead&&(i==0);
		int nhas0=has0||(i==0&&!lead);
		auto ret=dfs(x+1,i,nhas0,nlimt,nlead);
		int t=0;
		if(!lead) t=abs(i-lst)*ret.se%mod;
		ckadd(res.fi,ret.fi+t);
		ckadd(res.se,ret.se);
	}
	if(!limt&&!lead)
		f[x][lst][has0]=res;
	return res;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>s;n=s.size();
	memset(f,-1,sizeof f);
	auto ans=dfs(0,0,0,1,1);
	cout<<ans.fi;
	return 0;
}

Submission Info

Judge Result