Codeforces 908G – New Year and Original Order

题目链接

codeforces908G

题解

题目大意就是给你一个大小在\(10^{700}\)以内的数字,令\(S(n)\)表示\(n\)这个数字的数位按从小到大的方式排序后形成的数,现在给定一个数字\(n\),问\(\sum_{i=1}^nS(i)\),对\(1e9+7\)取模.


显然是一道数位\(dp\)的题目,我们设立\(dp\)方程\(f[i][j][k][l]\)表示考虑了前\(i\)位中有\(j\)位是否大于等于\(k\)的方案数.转移可以通过枚举下一位来转移.

尝试写出转移方程,发现不可描述……具体实现看代码,感觉还是很感人的……


By:Wahacer

2018.1.17

09:32

发表评论

电子邮件地址不会被公开。 必填项已用*标注