TopCode SRM 311 Div1 Medium SumThemAll

問題

lowerBound以上upperBound以下の整数に表れる数字を全て合計した和を求めよ。

（10から14なら、(1+0)+(1+1)+(1+2)+(1+3)+(1+4)）

制約条件

lowerBound, upperBound≦2*10^9

方針

n以下の整数に表れる数字を全て合計した和が求められればよい。

数字ごとに分けて動的計画法をする。
それぞれの数字が、何回出現したか、今までに元の整数より小さくなったか
の整数が何通りあるかを、それぞれの数字ごとに独立にDPして、
(場合の数)*(出現回数)*(数字)を合計する。

dp[i][j][k][l]を、i桁目まで見て、今注目している数字がjで、
k回その数字が出現していて、
l=0ならまだnより小さい数字が出現していないくて、
l=1ならnより小さい数字が出現しているような場合の数として足し合わせていく。

ソースコード

int d[20],n;
ll dp[20][10][20][2];
ll calc(int m){
	memset(dp,0,sizeof(dp));
	
	for(n=0;m;m/=10)d[n++]=m%10;
	reverse(d,d+n);
	
	rep(i,10)dp[0][i][0][0]=1;
	rep(i,n)rep(j,10)rep(k,i+1)rep(l,2){
		rep(nj,10)if(l||nj<=d[i]){
			int nl=l||nj<d[i];
			dp[i+1][j][k+(j==nj)][nl]+=dp[i][j][k][l];
		}
	}
	ll res=0;
	rep(i,10)rep(j,n+1)rep(k,2)res+=i*j*dp[n][i][j][k];
	return res;
}

class SumThemAll {
	public:
	long long getSum(int lowerBound, int upperBound) 
	{
		return calc(upperBound)-calc(lowerBound-1);
	}
};