[國家集訓隊]墨墨的等式

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

5

HINT

對于100%的數據，N≤12，0≤ai≤5*10^5，1≤BMin≤BMax≤10^12。

?

題目可以這樣變化一下：n個物品，可以用0-正無窮，問[l,r]區間內有多少價值可以湊出來。

聯系到最短路上面：

任選一個ai>0，如果一個價值k?ai+x(0≤x<ai,k≥0)可以被湊出來，那么顯然(k+1)?ai+x,(k+2)?ai+x,...都可以被湊出來（這樣x的范圍就是小于ai了）

顯然如果我們對于每個x都找到最小的k滿足k?ai+x可以被湊出來，這個問題就解決了，

如果滿足湊出x的最小花費是大于b的，那么就不能在[l,r]區間內湊出mn*k+x,這個數了，

否則的話，就計算[l,r]內有多少個可以湊出來。

最短路，spfa 時間復雜度O(n?ai?log2ai) 因為復雜度與ai有關，所以我們就選擇最小的ai了，

舉個例子：當最小的ai等于1時，那么自然區間內的所有數都可以湊出來了。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const ll inf=9e18;
const int N=5e5+5;
int q[N],mn,n,a[20];
ll dis[N];
bool vis[N];
void spfa()
{int h=0,w=1,x,y; q[1]=0; vis[0]=1;/*第一個能湊出的數就是0*/ while (h!=w){h++; if (h>mn+5) h=1; x=q[h];/*循環隊列，取出隊頭的數*/for (int i=1;i<=n;i++){y=(x+a[i])%mn;/*利用這個價值和其他價值組合所能達到的y，計算y的最小花費（因為只有計算最小花費），才能用mn湊出更多的滿足區間條件的數*/if (dis[y]>dis[x]+a[i]){dis[y]=dis[x]+a[i];if (!vis[y]){vis[y]=1;w++; if (w>mn+5) w=1; q[w]=y;}}}vis[x]=0;}
}ll query(ll x)
{ll ans=0;for (int i=0;i<mn;i++)if (dis[i]<=x) ans+=(x-dis[i])/mn+1; /*計算有多少個k滿足k*mn+i<=x，因為k>=0，所以還要加1*/return ans;
}/*windows 用I64d linux 用lld*/    
int main()
{mn=(1e9);ll L,R;scanf("%d%lld%lld",&n,&L,&R);for (int i=1;i<=n;i++) { scanf("%d",&a[i]); if (a[i]==0) { i--; n--; continue;} mn=min(mn,a[i]);}/*取出最小的an，但是不能為0，很好理解吧*/for (int i=1;i<mn;i++) dis[i]=inf;/*設達到每個k*mn+i(i<mn)的最小花費，所以數組dis中只有小于mn的i即可(*/spfa();printf("%lld\n",query(R)-query(L-1));return 0;
}

?