\(\text{CF908G}\)
题目描述
给\(n<=10^{700}\),问1到n中每个数在各数位排序后得到的数的和。答案膜 \(1e9+7\) 。
思路点拨
不是很难,自己想一会可以想出来。
因为 \(n\) 比较大,所以我们考虑数位dp。因为每一种数组产生的贡献十分复杂,所以我们将每一数字拆开统计贡献。
如果我们认为 \(n\) 表示数字的位数,相信 \(O(10^2n^3)\) 是比较好的出的。我们枚举一个数字 \(d\) ,则状态 \(f_{i,j,k,l}\) 表示目前考虑到第 \(i\) 位,比 \(d\) 小的有 \(j\) 位,比 \(d\) 大的有 \(k\) 位,目前有没有超出限制的 \(l=0/1\) 。转移比较简单,直接枚举下一位填什么,变动一下状态即可。但是不可以通过本题。
我们更改一下状态,我们定义 \(f_{i,j,k}\) 表示目前考虑到第 \(i\) 位,大于等于枚举的数 \(d\) 有 \(j\) 个,是否超出 \(limit\) 的 \(k=0/1\) 。转移比较类似。这样怎么计算贡献呢?因为 \(6\) 的数位可以拆成 \(5\) 的贡献加上 \(1\) 的贡献。所以我们这么统计是可行的。
标签:贡献,枚举,选练,动态,杂题,我们,数位 From: https://www.cnblogs.com/Diavolo/p/17735821.html