分布计数法

原题复现

小蓝在黑板上连续写下从 1 到 2023 之间所有的整数，得到了一个数字序列：$S = 12345678910111213...20222023$。小蓝想知道 $S$ 中有多少种子序列恰好等于 2023？

以下是 3 种满足条件的子序列（用中括号标识出的数字是子序列包含的数字）：

$1[2]34567891[0]111[2]1[3]14151617181920212223...$ $1[2]34567891[0]111[2]131415161718192021222[3]...$ $1[2]34567891[0]111213141516171819[2]021222[3]...$

注意以下是不满足条件的子序列，虽然包含了 2、0、2、3 四个数字，但是顺序不对：

$1[2]345678910111[2]131415161718192[0]21222[3]...$

解题思路

本题采用分部计数法,代码高效简洁且易于理解
思路很简单:

• 初始化4个变量a,b,c,d,分别代表序列2,20,202,2023出现的次数
• for i 遍历整个序列
• 读取到2 —> a += 1 , c += b
• 读取到0 —> b += a
• 读取到3 —> d += c

代码实现

a = b = c = d = 0
for i in range(1,2024):
    for j in str(i):
        match j:
            case '2':
                a += 1
                c += b
            case '0':
                b += a
            case '3':
                d += c
print(d)