企业官网建设流程全解析

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^9+7109+7取模。

输入格式

输入两行，每行一个数，分别是L LL和R RR。保证1 ≤ L ≤ R ≤ 10 100 1 \leq L \leq R \leq 10^{100}1≤L≤R≤10100。

输出格式

输出一个数，表示答案。

输入输出样例 #1

输入 #1

1 100

输出 #1

54

说明/提示

C++实现

#include<iostream>#include<algorithm>#include<vector>#definelllonglongusingnamespacestd;intx,len,s[101],dp[101][2][10];intdfs(constintp,constinte,constintlast=0){// 求 dpif(p==len)return1;elseif(dp[p][e][last]>=0)returndp[p][e][last];ll ret=0;for(inti=last;i<10;i++)if(e&&i>s[p])break;elseret+=dfs(p+1,e&(i==s[p]),i);returndp[p][e][last]=ret%1000000007;}llsolve(conststring&n){// 求 Mif(n=="0")return1;len=n.size();for(inti=0;i<len;i++)s[i]=n[i]-'0';for(auto&i:dp)for(auto&j:i)for(auto&k:j)k=-1;returndfs(0,1);}stringsub1(string s){// 高精度字符串减1if(s=="1")return"0";vector<int>v;for(charc:s)v.push_back(c-'0');reverse(v.begin(),v.end());v[0]--;for(size_t i=0;i+1<v.size();i++)if(v[i]<0)v[i]+=10,v[i+1]--;while(!v[v.size()-1])v.pop_back();reverse(v.begin(),v.end());s="";for(size_t i=0;i<v.size();i++)s+=char(v[i]+48);returns;}intmain(){cin.tie(nullptr)->sync_with_stdio(false),cout.tie(nullptr);string l,r;cin>>l>>r;cout<<(solve(r)-solve(sub1(l))+1000000007)%1000000007;return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容