题目描述

小红定义了一个正整数是好数，当且仅当数位中，奇数的数量等于偶数的数量，例如，"1124" 是好数。

现在小红想知道，$[l,r]$ 区间内有多少好数，你能帮帮他吗？

题解

抽象一下题意，给你一个区间，判断在 $[l, r]$ 中，当前数位满足奇数位和偶数位的个数相同的数有多少个。

看到这种给一个区间 $[l, r]$ 并要求满足条件的数的个数，一般都是用数位 DP 解决。

之前没有了解过数位 DP 的uu，可以看看 灵神讲的 数位 DP 通用模板

将 $n$ 转换成字符串 $s$，定义 $dfs(i,\textit{isOk},\textit{isLimit},\textit{isNum})$ 表示构造第 $i$ 位及其之后数位的合法方案数，其余参数的含义为：