bzoj2118 墨墨的等式

Description

墨墨突然对等式很感兴趣，他正在研究a1x1+a2y2+…+anxn=B存在非负整数解的条件，他要求你编写一个程序，给定N、{an}、以及B的取值范围，求出有多少B可以使等式存在非负整数解。

Input

输入的第一行包含3个正整数，分别表示N、BMin、BMax分别表示数列的长度、B的下界、B的上界。输入的第二行包含N个整数，即数列{an}的值。

Output

输出一个整数，表示有多少b可以使等式存在非负整数解。

Sample Input

2 5 10
3 5

Sample Output

HINT

对于100%的数据，N≤12，0≤ai≤5*10^5，1≤BMin≤BMax≤10^12。

正解：$spfa$。

其实这题思路并不难，但是很难想到啊。。

其实这是一个完全背包问题，然后求一个区间是否可以被选出来。

我们考虑一个式子：$ax+k$，其中$k<a$，$a$是任意一个物品的重量。

那么如果$ax+k$可以被表示出来，$a(x+1)+k$肯定也可以被表示出来，$a(x+p)+k$同理。

那么我们可以任选一个物品(直接选重量最小的就行了)，假设它的重量为$m$，构造一个$[0,m-1]$这$m$个点的图。

然后$dis[i]$表示在$ mod m$意义下为$i$的数中，实际能凑出的最小的数是什么，直接跑最短路即可。

最后枚举每一个点，算出它加上$xm$以后能凑出的$[minb,maxb]$中的数量，加起来就行了。

 1 #include <bits/stdc++.h>
 2 #define il inline
 3 #define RG register
 4 #define ll long long
 5 #define N (500010)
 6 
 7 using namespace std;
 8 
 9 int vis[N],a[N],n,m;
10 ll dis[N],ql,qr;
11 
12 queue <int> Q;
13  
14 il int gi(){
15   RG int x=0,q=1; RG char ch=getchar();
16   while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
17   if (ch=='-') q=-1,ch=getchar();
18   while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
19   return q*x;
20 }
21 
22 il ll query(RG ll x){
23   RG ll res=0;
24   for (RG int i=0;i<m;++i){
25     if (dis[i]>x) continue;
26     res+=(x-dis[i])/m+1;
27   }
28   return res;
29 }
30 
31 int main(){
32 #ifndef ONLINE_JUDGE
33   freopen("equal.in","r",stdin);
34   freopen("equal.out","w",stdout);
35 #endif
36   n=gi(),cin>>ql>>qr,m=1000000;
37   for (RG int i=1;i<=n;++i){
38     a[i]=gi(); if (!a[i]){ --n,--i; continue; }
39     m=min(m,a[i]);
40   }
41   for (RG int i=1;i<m;++i) dis[i]=qr+1; Q.push(0),vis[0]=1;
42   while (!Q.empty()){
43     RG int x=Q.front(),v; Q.pop();
44     for (RG int i=1;i<=n;++i){
45       v=(x+a[i])%m;
46       if (dis[v]>dis[x]+a[i]){
47     dis[v]=dis[x]+a[i];
48     if (!vis[v]) vis[v]=1,Q.push(v);
49       }
50     }
51     vis[x]=0;
52   }
53   printf("%lld
",query(qr)-query(ql-1)); return 0;
54 }