打卡信奥刷题（3590）用C++实现信奥题 P11557 [ROIR 2016] 有趣数字 (Day 2)

P11557 [ROIR 2016] 有趣数字 (Day 2)题目背景翻译自 ROIR 2016 D2T3。题目描述如果一个整数的各个数位按非递减顺序排列我们称这个数是“有趣的”。例如1145 , 2333 , 1377777 1145,2333,13777771145,2333,1377777都是“有趣的”。给定L , R L,RL,R求出[ L , R ] [L,R][L,R]中有趣的数字的个数对10 9 7 10^971097取模。输入格式输入两行每行一个数分别是L LL和R RR。保证1 ≤ L ≤ R ≤ 10 100 1 \leq L \leq R \leq 10^{100}1≤L≤R≤10100。输出格式输出一个数表示答案。输入输出样例 #1输入 #11 100输出 #154说明/提示子任务是否捆绑分值特殊性质1 11是21 2121L 1 L 1L1R ≤ 1000 R \leq 1000R≤10002 22否22 22221 ≤ L ≤ R ≤ 10 18 1 \leq L \leq R \leq 10^{18}1≤L≤R≤10183 33否24 2424L 1 L 1L1R 10 k R 10^kR10k其中2 ≤ k ≤ 100 2 \leq k \leq 1002≤k≤1004 44否33 33331 ≤ L ≤ R ≤ 10 100 1 \leq L \leq R \leq 10^{100}1≤L≤R≤10100C实现#includeiostream#includealgorithm#includevector#definelllonglongusingnamespacestd;intx,len,s[101],dp[101][2][10];intdfs(constintp,constinte,constintlast0){// 求 dpif(plen)return1;elseif(dp[p][e][last]0)returndp[p][e][last];ll ret0;for(intilast;i10;i)if(eis[p])break;elseretdfs(p1,e(is[p]),i);returndp[p][e][last]ret%1000000007;}llsolve(conststringn){// 求 Mif(n0)return1;lenn.size();for(inti0;ilen;i)s[i]n[i]-0;for(autoi:dp)for(autoj:i)for(autok:j)k-1;returndfs(0,1);}stringsub1(string s){// 高精度字符串减1if(s1)return0;vectorintv;for(charc:s)v.push_back(c-0);reverse(v.begin(),v.end());v[0]--;for(size_t i0;i1v.size();i)if(v[i]0)v[i]10,v[i1]--;while(!v[v.size()-1])v.pop_back();reverse(v.begin(),v.end());s;for(size_t i0;iv.size();i)schar(v[i]48);returns;}intmain(){cin.tie(nullptr)-sync_with_stdio(false),cout.tie(nullptr);string l,r;cinlr;cout(solve(r)-solve(sub1(l))1000000007)%1000000007;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容