yukicoder : No.528 10^9と10^9+7と回文

DもEもしんどかった。
http://yukicoder.me/problems/no/528

問題

整数Nが与えられる。
1～Nの整数のうち(leading zeroを除き)10進数表記が回文となるものの個数を答えよ。

解法

まずはleading zeroを許可したケースを考える。
桁数が小さい場合は総当たりをしてもいいので、ある程度桁数が多い場合のみ考える。
先頭桁をX、末尾桁をY、桁数をDとしてX*****Yのように書ける整数を考え、0000000～X*****Yの範囲で回文となるものの数を考えよう。

先頭桁がX未満、すなわち0～(X-1)の場合、以降の桁は任意の数字を書けるので、末尾の桁を先頭の桁と合わせることを考えるとX*f(D-2)通り回文を作れる。
f(k)はleading zeroを許容したk桁の数で表現できる回文の数で、f(k)=10^ceil(k/2)である。

次に先頭桁をXとした場合の数を足す。

• X≦Yの場合、末尾の数をXを取ることを考えると、******の部分の回文の数と等しい
• X＞Yの場合、末尾の数をXを取るためには繰り下がりが生じるので、((******の部分)-1)の回文の数と等しい

あとはこれにleading zeroを許可しないケースを同様に考えればよい。

int N;
string S;
ll p10[101010];
ll num[101010];
ll sum[101010];
ll mo;

int small(deque<int>& D,int first) {
	int v=0,ret=0;
	FORR(c,D) v=v*10+c;
	for(int i=first;i<=v;i++) {
		char buf[10];
		string a,b;
		if(first) {
			sprintf(buf,"%d",i);
			a=buf;
		}
		else {
			sprintf(buf,"%06d",i);
			a=buf;
			a=a.substr(a.size()-D.size());
		}
		b=a;
		reverse(ALL(b));
		if(a==b) ret++;
	}
	return ret;
}

ll gogo(deque<int>& D,int first=0) {
	int i,j,k,l,r,x,y;
	
	if(D.size()<=4) return small(D,first);
	
	ll ret=0;
	if(first) {
		ret += 9*sum[D.size()-1];
		(ret += (D[0]-1)*10*num[D.size()-2])%=mo;
	}
	else {
		(ret += D[0]*10*num[D.size()-2])%=mo;
	}
	
	int del=D[0]>D.back();
	D.pop_front();
	D.pop_back();
	for(i=D.size()-1;i>=0&&del;i--) {
		D[i]--;
		if(D[i]>=0) del=0;
		else D[i]=9;
	}
	if(del==0) ret += gogo(D);
	return ret%mo;
}

ll hoge() {
	int i,j,k,l,r,x,y; string s;
	
	p10[0]=1;
	FOR(i,100001) {
		p10[i+1]=p10[i]*10%mo;
		if(i==0) num[i]=0;
		else num[i]=p10[(i-1)/2]%mo;
		sum[i]=((i==0)?0:sum[i-1])+num[i];
	}
	
	deque<int> T;
	FORR(c,S) T.push_back(c-'0');
	return gogo(T,1);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	
	mo=1000000000;
	cout<<hoge()<<endl;
	mo=1000000007;
	cout<<hoge()<<endl;
	
}

まとめ

もっとシンプルに書けないものか。