直接对 $2^n$ 个子集求和并逐个统计十进制中数字 4 的个数，在 $n \le 40$ 时是不可行的（$2^{40} \approx 10^{12}$）。

为了优化计算，我们可以按十进制数位单独统计贡献：

设 $P = 10^k$（$k = 0, 1, 2, \dots$，分别对应个位、十位、百位……）。

任何一个非负整数 $S$ 的第 $k$ 位数字（从右往左数第 $k$ 位，从 $0$ 开始索引）等于 4，当且仅当：

$$S \bmod 10^{k+1} \in [4 \times 10^k, \, 5 \times 10^k - 1]$$

所以：所有子集和中数字 4 的总个数 $= \sum_{k=0}^{9} (\text{数位 } k \text{ 上数字为 4 的子集和个数})$。

考虑折半搜索。将集合划分为两半：

• 前半部分 $n_1 = \lfloor n/2 \rfloor$ 个数，其所有子集和集合为 $S_1$。
• 后半部分 $n_2 = n - n_1$ 个数，其所有子集和集合为 $S_2$。

对于任意一对子集和 $x \in S_1, y \in S_2$，整体子集和为 $S = x + y$。根据模运算性质：

$$(x + y) \bmod 10^{k+1} = \big((x \bmod 10^{k+1}) + (y \bmod 10^{k+1})\big) \bmod 10^{k+1}$$

令 $M = 10^{k+1}$，由于 $0 \le x \bmod M < M$ 且 $0 \le y \bmod M < M$，加和 $(x \bmod M) + (y \bmod M)$ 的范围在 $[0, 2M - 2]$ 之间。

因此，使 $(x + y) \bmod M \in [4P, 5P - 1]$ 成立的条件等价于无取模加和落在以下两个互斥区间之一：

1. 未产生模溢出：$x \bmod M + y \bmod M \in [4P, 5P - 1]$。
2. 产生了一次模溢出：$x \bmod M + y \bmod M \in [4P + M, 5P - 1 + M] = [14P, 15P - 1]$。

如果对每个数位 $k$ 都将 $S_1 \bmod M$ 和 $S_2 \bmod M$ 重新排序，单次排序复杂度为 $O(2^{n/2} \log 2^{n/2})$，不一定好通过。

但由于低位在之前的步骤中已经排序完成，根据最低位优先的基数排序：每次递增 $k$ 时，只需对 $S_1$ 和 $S_2$ 按照当前位数字 $d_k = \lfloor S / 10^k \rfloor \bmod 10$ 进行一次稳定计数排序，复杂度仅为 $O(2^{n/2})$。

排序后，数组 $A = S_1 \bmod M$ 和 $B = S_2 \bmod M$ 自然保持有序。 利用双指针在两个有序数组中统计满足 $L \le A[i] + B[j] \le R$ 的 $(i, j)$ 对数，单次统计时间复杂度为 $O(2^{n_1} + 2^{n_2})$。