AtCoder ARC #090 : F - Number of Digits

こっちの方が結果的には楽だった。
https://beta.atcoder.jp/contests/arc090/tasks/arc090_d

問題

正整数xに対し、f(x)はxを10進表記したときの桁数とする。
整数Sが与えられる。整数の区間x∈[L,R]に対し、sum_x f(x)=Sとなるような区間[L,R]は何通りか。

解法

L＜10^8のケースは、尺取り法の要領でRの候補を求めていけよい。
Sが10^8以下なので、L≧10^8の場合、RはLと同じ桁数か、せいぜい1つ大きな桁数にしかなりえない。

よって、[L,R]の区間長Pを1～Sの範囲で総当たりしよう。
[L,R]の間でf(x)は1つしか変わらないので、PがSの倍数ならf(L)=f(R)=S/P、そうでないならf(L)=S/P、f(R)=S/P+1と一意に決まる。
後者の場合、L,Rも一意に決まる。
前者の場合、LとRは桁数が一致する範囲で自由に取れるので、9*10^(S/P)-P+1通り取れる。

ll num[1010];
int S;
ll mo=1000000007;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	num[1]=9;
	for(i=2;i<=10;i++) num[i]=num[i-1]*10;
	
	cin>>S;
	ll L,R=1;
	ll tot=1;
	ll NL=10,NR=10,LC=1,RC=1;
	ll ret=0;
	for(L=1;L<100000000;) {
		while(tot<S) {
			R++;
			if(R==NR) NR*=10,RC++;
			tot+=RC;
		}
		if(tot==S) ret++;
		tot-=LC;
		L++;
		if(L==NL) NL*=10,LC++;
	}
	for(i=1;i<=S;i++) {
		L=S/i;
		if(L<=8) continue;
		if(S%i) {
			ret++;
		}
		else {
			(ret+=9*modpow(10,L-1)-i+1+mo)%mo;
		}
	}
	cout<<ret%mo<<endl;
}

まとめ

区間長で総当たりすることをさっさと思いつけて良かった。