递归，举个例子 51234 = 50000 + 1000+ 200+ 30 + 4
低位可以对高位做贡献，复杂度log(n)

数位dp很容易做出来。部分代码
long long dfs(int pos, bool bound)
{
if(pos == -1) return 0;
if(!bound && ~dp[pos]) return dp[pos];

int end = bound ? dig[pos]-'0' : 9;
long long ret = 0;
for(int i=0; i<=end; i++)
{
ret += dfs(pos-1, bound && i == end);
if(i == 1)
{
if(bound && i == end) ret += q[pos] + 1;
else ret += p[pos];
}
}
if (!bound) dp[pos] = ret;
return ret;
}