题解

思路

系数为零的项不会改变等式右侧，因此可以忽略。若所有系数都为零，那么只有 $0$ 可表示；由于本题 $l\ge 1$，答案为 $0$。

下面设最小的正系数为 $m$。如果某个数 $v$ 可表示，那么 $v+m,v+2m,\ldots$ 也都可表示。因此，对每个模 $m$ 的余数，只需知道该余数下最小的可表示数。

子任务 1

此时 $r\le 10$。可以逐个枚举 $b\in[l,r]$，再递归枚举每个系数使用多少次，判断是否能恰好组成 $b$。范围很小，搜索量可以直接承受。

子任务 2

此时 $r\le 10^6$。建立布尔数组表示每个不超过 $r$ 的数是否可表示，从 $0$ 开始进行完全背包转移。最后统计区间 $[l,r]$ 中的可达位置。

时间复杂度为 $O(nr)$，空间复杂度为 $O(r)$。

做法

把每个余数 $0,1,\ldots,m-1$ 看作一个点。对于每个正系数 $a_i$，从余数 $u$ 向 $(u+a_i)\bmod m$ 连一条长度为 $a_i$ 的边。

从余数 $0$ 出发走过若干条边，路径长度正好是所选系数之和。因此，从 $0$ 到余数 $t$ 的最短路长度 $d_t$，就是所有模 $m$ 余 $t$ 的可表示数中的最小值。边权非负，可以用 Dijkstra 算法求出全部 $d_t$。

设 $F(X)$ 表示 $[0,X]$ 中可表示数的个数。若 $d_t\le X$，则余数 $t$ 对答案的贡献为

对所有余数求和即可得到 $F(X)$，最终答案是 $F(r)-F(l-1)$。

复杂度

满分算法的时间复杂度为 $O(nm\log m)$，空间复杂度为 $O(m)$，其中 $m$ 是最小正系数。

正确性说明

余数图中的任意一条从 $0$ 出发的路径，都对应选择若干个系数，其路径长度就是一个可表示数；反之，任意一种非负整数解都可以按使用次数排列成一条对应路径。因此最短路 $d_t$ 恰好是余数 $t$ 下最小的可表示数。

又因为 $m$ 本身是一个可用系数，所以同一余数下从 $d_t$ 开始、每增加 $m$ 得到的数全部可表示；比 $d_t$ 小的同余数没有可表示数。计数公式覆盖且仅覆盖所有可表示数，区间差分因此得到正确答案。