UVa 11038 How many 0s?

問題

n以上m以下の整数を10進数で全て書いたとき、
書かれる0の数は合計いくつか、求めよ。

制約条件

0≦n, m<2^32

方針

桁DPをすれば求まるが、もう少し簡単に出来る。


0〜nの数に含まれる0の個数を数えられればよい。
nの桁数をmとする。
m桁でleading zeroを許して数え上げをすれば、m桁より少ない桁数の数の0の数も数え上げられる。


i桁目が0であるような数でn以下のものがいくつあるかを数えたい。
(a)i(b)
これは、
i桁目が0でないときは、a * (bの部分を0〜9999にする場合の数)
i桁めが0であるときは、(a - 1) * (bの部分を0〜9999にする場合の数) + (bの部分をb以下にする方法)
に等しい。

ソースコード

ll calc(ll n){
	if(n < 0) return 0;
	ll res = 1, base = 1, left = 0;
	while(1){
		ll d = n % 10;
		n /= 10;
		
		if(n == 0) break;
		if(d) res += n * base;
		else res += (n - 1) * base + left + 1;
		
		left += base * d;
		base *= 10;
	}
	return res;
}