TopCoder SRM 855 : Div1 Medium NumReverseHard

考え方は合っていたけど、バグを大量に埋め込んで詰めるのに苦戦した。
https://community.topcoder.com/stat?c=problem_statement&pm=18240

問題

整数A,Bが与えられる。
AからBの各整数xについて、xとxの桁の並び順を反転したもののうち大きい方の総和を求めよ。

解法

f(v) := 1～vの各整数について、xとxの桁の並び順を反転したもののうち大きい方の総和
とすると、f(B)-f(A-1)が解。あとはf(v)の求め方を考えよう。

まず1～vを単純に総和を取り、その後反転による寄与分を計上しよう。
先頭と末尾(x-1)桁が一致し、先頭x桁目の値Lより末尾x桁目の値Rが大きくなる場合を総当たりする。
またその間にy桁整数が入るとする。

全体の桁数(2x+y)がvより桁が小さい場合を考える。
先頭(x-1)桁は、leading zeroを持たない9*10^(x-2)通りが考えられる。
よって、LとRを反転させることで(R-L)**1*9*10^(x-2)*10^yだけ解が増加する。

2x+yがvと桁数が同じ場合、先頭(x-1)桁がvを超えない範囲になるので注意。
また、先頭x桁がLと一致する場合、真ん中のyを定めてく間で全体がvを超えないようにする必要がある。
これは桁DPで数え上げて行けばよい。

const ll mo=1000000007;
ll p10[22];
ll p10m[22];

class NumReverseHard {
	public:
	ll rev(ll a) {
		ll v=0;
		while(a) v=v*10+a%10,a/=10;
		return v;
	}
	
	ll hoge(ll v) {
		//単純な和
		if(v<=0) return 0;
		ll ret=v%mo*((v+1)%mo)%mo*(mo+1)/2%mo;
		int len=to_string(v).size();
		
		int pre,mid,L,R,i,j;
		for(pre=1;pre*2<=len;pre++) for(mid=0;pre*2+mid<=len;mid++) {
			for(L=0;L<=9;L++) {
				if(pre==1&&L==0) continue;
				
				ll mnum=p10m[mid];
				ll num;
				if(pre*2+mid<len) {
					num=(pre==1)?1:(9*p10m[pre-2]);
				}
				else {
					ll pref=v/p10[mid+pre];
					num=(v-p10[len-1])/p10[mid+pre+1]+1;
					if(L>=pref%10) num--;
				}
				num%=mo;
				
				for(R=L+1;R<=9;R++) {
					ll add=(L-R)*p10m[pre-1]+(R-L)*p10m[pre+mid];
					add=(add%mo+mo)%mo;
					(ret+=add*mnum%mo*num%mo)%=mo;
				}
				
				if(pre*2+mid==len&&L==v/p10[mid+pre]%10) {
					pair<ll,ll> from[2]={};
					from[0].first=1;
					from[0].second=L*(p10m[pre-1]-p10m[pre+mid]+mo)%mo;
					for(i=pre+mid-1;i>=pre;i--) {
						pair<ll,ll> to[2]={};
						int d=v/p10[i]%10;
						
						ll m=(p10m[len-1-i]-p10m[i]+mo)%mo;
						
						FOR(j,10) {
							(to[1].first+=from[1].first)%=mo;
							(to[1].second+=from[1].second+from[1].first*j%mo*m)%=mo;
							if(j<d) {
								(to[1].first+=from[0].first)%=mo;
								(to[1].second+=from[0].second+from[0].first*j%mo*m)%=mo;
							}
							else if(j==d) {
								(to[0].first+=from[0].first)%=mo;
								(to[0].second+=from[0].second+from[0].first*j%mo*m)%=mo;
							}
						}
						swap(from,to);
					}
					
					for(int R=L+1;R<=9;R++) {
						ret+=from[1].second;
						ret+=from[1].first*R%mo*(p10m[pre+mid]-p10m[pre-1]+mo)%mo;
						if(R*p10[pre-1]+rev(v)%p10[pre-1]<=v%p10[pre]) {
							ret+=from[0].second;
							ret+=from[0].first*R%mo*(p10m[pre+mid]-p10m[pre-1]+mo)%mo;
						}
					}
					
				}
				
				
			}
			ret%=mo;
		}
		
		
		
		
		cout<<v<<" "<<ret<<endl;
		return ret;
	}
	
	
	int getsum(long long A, long long B) {
		int i;
		p10[0]=1;
		p10m[0]=1;
		FOR(i,19) {
			p10[i+1]=p10[i]*10;
			p10m[i+1]=p10[i+1]%mo;
		}
		return (hoge(B)-hoge(A-1)+mo)%mo;
	}
}

まとめ

考え方があっていただけにミスがもったいないな。

*1:10^(x+y)-10^(x-1