Steven_MengのBlog

传送门

首先,大家都可以看出来,这道题是一个多重背包,设$f(i)$为和为$i$可不可行,那么假设$k$为${a_n}$中的一个数,且$f(s)==1$,我们把$f(s+k \times 1)$,$f(s+k \times 2)$,$f(s+k \times 3)$,….都设为$1$

但是,作为一个不知道高到哪里去的膜法师,你发现这样子搞太$Naive$了,这样要做无穷次,而且得出来的数$s+k \times 1 , s+k \times 2,s + k \times 3$取值范围也是正无穷,于是,你决定给它取一个膜,假设我们膜的是$ha$

发现$s+k \times {(i+ha)} == s+k \times i (\mod ha)$,所以连的边最多$ha$条,取值范围也变成$[0,ha)$,你不禁叫了一声:

吼啊!

如图:

于是,此题的具体思路就有了,我们对于每一个$s \in [0,ha)$建立一个点,把$s$和$(s+a[i]) \mod ha$连一条边,边权为$a[i]$,从$s=0$跑最短路,得到$dist$数组。

考虑差分得出$[L,R]$中$B$有多少种取值,

 评论