大意

给定长度为 $n$ 的系数数组 $a_i$ 和 $l,r$ ，求出长度为 $n$ 的数组 $x_i(x_i\in\mathbb{N})$ 使得：

$$l\leq \sum_{i=1}^na_ix_i\leq r $$

问 $x_i$ 数组有多少个。

$n\leq 12,1\leq l\leq r\leq 9\times10^{11},1\leq a_i\leq5\times10^5$ 。

分析

本题很巧妙。令 $m=\min\{a_i\}$ ，然后对于所有的 $x_i$ 都可以根据 $\sum_{i=1}^na_ix_i$ 模 $m$ 的余数归为一类。把每一类作为一个节点，每个节点向它的值加上一个 $a_i$ 的那一类连边权为 $a_i$ 的线。然后求最短路， $\mathrm{distance}(u)$ 就表示结点 $u$ 所代表的类的最小值。

这个模型很酷炫，记记。