一类与数位相关的计数问题

$f \colon \mathbb{Z}_{>0} \to \{0, 1\}$ 是关于正整数的十进制表示的函数 。

给你一个正整数 $N$，求 $ F(N) := \sum_{i=1}^{N} f(i)$。

用 $|N|$ 表示 $N$ 的位数。用 $N_i$ 表示 $N$ 的十进制表示里从左往右第 $i$ 个数字，$i$ 从 $1$ 开始。
$x$ 是正整数。
用 $P(x, n)$ 表示 $N$ 的前 $n$ 个数字成的数，即 $P_N(n) := \floor{N / 10^{|N| - n}}$。
用 $S(x, n)$ 表示 $\sum_{i = x \cdot 10^n} ^{(x + 1) \cdot 10^{n} - 1 }
f(i)$。

用 $T(n)$ 表示 $\sum_{i = 10^{n - 1}}^{10^{n} -1} f(i)$。

则
\begin{equation*}
\begin{split}
F(N) = f(N) + \sum_{i = 1}^{|N| - 1} T(i) + \sum_{i = 1}^{N_1 - 1} S(i, |N| - 1) \\ + \sum_{i = 1}^{|N| - 1} \sum_{j = 0}^{N_{i + 1}} S(10 \cdot P(n, i) + j, |N| - i - 1)
\end{split}
\end{equation*}

一类与数位相关的计数问题

原文：https://www.cnblogs.com/Patt/p/14690292.html