题面

题解

考场上蠢了……这么简单的东西都想不到……

首先排序加去重。

先来考虑一下，形如

\[a_1x_1+a_2x_2+...a_nx_n=w,a_1<a_2<...<a_n,x_i\geq 0\]

的方程该怎么判断是否有解

首先，把两边都放到模\(a_1\)的意义下，就是

\[a_2x_2+...a_nx_n\equiv w\pmod{a_1}\]

然后是一个神仙的转化，我们设有\(a_1\)个点，分别代表\(0,1,...,a_1-1\)，对于每一个点\(u\)，都连出去\(n-1\)条边，分别连向\((a+a_i)\%a_1\)，代价为\(a_i\)。那么我们对这个图跑一遍最短路，如果\(dis_{w\%a_1}\leq w\)，那么显然可以用这条最短路上的所有边加上若干个\(a_1\)构成\(w\)，否则的话肯定不行

那么对于大于等于\(L\)的部分我们可以暴力\(dp\)，设\(dp_{i,j}\)表示选了\(i\)个数，其中这\(i\)个数的和模\(a_1\)后为\(j\)（\(a_1\)就是最小的数），这\(i\)个数的和最小是多少，直接大力转移即可。

最后用\(dp_{i,j}\)更新\(dis_j\)，然后从每一个不为\(inf\)的\(dis_j\)出发，以所有\(a_i< L\)为边，跑多源最短路就行了

ps：其实严格来说如果\(a_1\geq L\)的话会发现上面的做法是错的，不过错的只有最短路那部分，暴力\(dp\)还是正确的，所以忽视这一点也没问题

//minamoto#include
    
     #define R register#define ll long long#define inf 0x3f3f3f3f#define fp(i,a,b) for(R int i=a,I=b+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template
      
       inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}template
       
        inline bool cmax(T&a,const T&b){return a
        
         '9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}const int N=55,M=10005;struct node{    int u,d;    node(){}    node(R int U,R int D):u(U),d(D){}    inline bool operator <(const node &b)const{return d>b.d;}};priority_queue
         
          q;bitset
          
           f[N];int a[N],vis[M];int n,m,p,l,c,lim,u,v;ll w,dis[M],dp[N][M];void mdzz(){ memset(dis,0x3f,sizeof(dis)); fp(i,0,a[1]-1){ fp(j,0,c)cmin(dis[i],dp[j][i]); if(dis[i]!=inf)q.push(node(i,dis[i])); } while(!q.empty()){ u=q.top().u,q.pop(); if(vis[u])continue;vis[u]=1; fp(i,2,p)if(cmin(dis[v=(u+a[i])%a[1]],dis[u]+a[i]))q.push(node(v,dis[v])); }}int main(){// freopen("testdata.in","r",stdin); freopen("bag.in","r",stdin); freopen("bag.out","w",stdout); n=read(),m=read(); fp(i,1,n)a[i]=read(); sort(a+1,a+1+n),n=unique(a+1,a+1+n)-a-1; l=read(),c=read(),p=lower_bound(a+1,a+1+n,l)-a-1; memset(dp,0x3f,sizeof(dp)); dp[0][0]=0; fp(i,p+1,n)fp(k,0,c-1)fp(j,0,a[1]-1){ v=(j+a[i])%a[1]; cmin(dp[k+1][v],dp[k][j]+a[i]); } mdzz(); while(m--){ w=read(); puts(dis[w%a[1]]<=w?"Yes":"No"); } return 0;}