题目来源：http://www.51nod.com/Challenge/Problem.html#problemId=1009

题解1

感谢优秀博客： https://blog.csdn.net/adusts/article/details/80730383
以上博客写的很详细，这里稍作总结
算法思想
如输入：n=43102，则输出的是1`4321中1出现的次数

• 1.遍历43102的每一位(i=1,2,3,4,5)，遍历顺序1-n，记录第i位出现1的次数ans，然后相加得结果
  2.对于第i位数，如果小于1(如十位数1)，ans = 43110 {10,11,19,…,43110,43119}
  如果大于1(如千位数3)，ans = (4+1)1000 {1000,1001,…,1999,21000,…,21999,31000,…41999}
  如果等于1(如百位数1)，ans = 43*100+2 {100,…,199,1100,…,43199,43101,43102}
  (注：链接博客中等于1的情况有点错误)
  按此规律，代码如下：

  ll sum(ll n)
  {
      ll i = 1, front = 0, after = 0, now = 0;
      ll ans = 0;
      while(n/i)
      {
          front = n / (10*i);
          after = n % i;            // after = n - n/i%i;
          now = n % (10*i) / i;    // now = n/i%10;
          if(now == 0)
              ans += front*i;
          if(now == 1)
              ans += (front*i + after + 1);
          if(now > 1)
              ans += (front+1)*i;
          i *= 10;
      }
      return ans;
  }

题解2-数位dp

参考我的dp-digit: https://www.weayer.top/2020/03/10/dp-digit/
算法思想
1.对于10^i内记录1出现次数
2.同样如n=43102，遍历每一位数，但遍历顺序从n到1，还有不同的是这里将其拆为m[] = {40000,3000,100,0,2}
对于第i位，记录m[i-1]内1出现的次数res，而10^i内1的次数已经得到了(如千位数3，ans = 3*dp[3])
当然单独计算ans然后累加肯定是不行的，第i位数的贡献值还与低位的数有关(如千位数3，仅记录了3000内1的次数，后面102同样会用到3)所以类似题解1

typedef long long ll;
ll a[25], dp[25], digit[25];
void init()      //统计10^(i-1)内各数出现次数,dp[i]存储 
{               //dp[i] = 10*dp[i-1] + 10^(i-1)
    digit[0] = 1;
    for(int i = 1; i <= 20; ++i)
    {
        dp[i] = dp[i-1]*10 + digit[i-1];
        digit[i] = digit[i-1] * 10;
    }
}

ll solve(ll m)
{
    ll ans = m, len = 0, sum = 0;
    while(m)
    {
        a[++len] = m % 10;
        m /= 10;
    }
    for(int k = len; k >=1; --k)
    {
        sum += a[k] * dp[k-1];
        ans -= a[k] * digit[k-1];
        if(a[k] == 0)
            continue;
        if(a[k] == 1)
            sum += (ans + 1);
        else
            sum += digit[k-1];
    }
    return sum;
}