给一个整数n， n<10^18，拆成若干段，每段加起来求和。输出所有和中 <= k 的个数。k<10^18。c++代码

这是一道比较有意思的数位 DP 题目。我们先考虑一个朴素的 DP 做法：设 $dp_{i,j}$ 表示考虑到第 $i$ 位，前 $i$ 位数字组成的数加起来小于等于 $j$ 的方案数。状态转移方程为：

$$
dp_{i,j} = \sum_{k=0}^9 dp_{i-1,j-k}
$$

但是这个做法的时间复杂度是 $O(nk)$，因此无法通过本题。我们需要优化这个状态转移方程。

我们可以对数位进行分组，设 $s$ 表示这个数位分组后的组数，$g_i$ 表示第 $i$ 个组的数位个数，$p_i$ 表示第 $i$ 个组的权值（即这个组内每个数位对应的数），$f_{i,j}$ 表示前 $i$ 个组的和不超过 $j$ 的方案数。那么我们可以得到状态转移方程：

$$
f_{i,j} = \sum_{k=0}^9 \sum_{l=0}^j f_{i-1,j-lp_i-kg_i}
$$

其中 $l$ 表示前 $i-1$ 个组的和，$kg_i$ 表示当前位数字为 $k$ 时的贡献。这个状态转移方程的时间复杂度为 $O(skn)$，可以通过本题。

具体实现时，我们可以先对原数进行分组，然后按照上述状态转移方程进行 DP，最后统计答案时枚举 $f_{s,j}$ 的值即可。

下面是代码实现：