一道找规律好题...
首先,我们肯定只能一位一位的统计答案,考虑从高位向低位统计,显然这样要方便的多.
对于第i位,我们统计从$a[i+1]*10^i+0$到$a[i+1]*10^i+a[i]*10^{i-1}-1$对答案的贡献.
($a[i]$表示原数的第i位)
显然0~10^(i-1)-1中的每一个数都是作为上述某个数的一部分出现过的,且他们的出现次数都为a[i](第i位从0~a[i]-1,最后一位除外,出现a[i]+1次).所以有$(a[i]+(i==1))*sum[i-1]$的贡献.
(sum[i-1]表示0~10^(i-1)-1对答案的总贡献)
然后考虑剩下的高位对答案的贡献.首先考虑第i位,第i位的数字从0~a[i]-1出现的次数都为10^(i-1),第i位以前的数字与原数第i位以前的数字相同,所以前i位对答案的贡献为:
$(a[i]+(i==1))*s[i+1]+num[a[i]-(i!=1)])*ten[i-1].$
(s[i+1]表示前i-1位的前缀和,注意是从高位往低位,num[i]表示0~9的前缀和)
Eg:
123
i==3 统计0~99 (1*0+0)*10^2+1*900
i==2 统计100~119 (2*1+1)*10^1+2*45
i==1 统计120~123 (3*4+6)*10^0+4*0
Ans=1038