數論+spfa算法 bzoj 2118 墨墨的等式

2118: 墨墨的等式

Time Limit: 10 Sec  Memory Limit: 259 MB

Submit: 1283  Solved: 496

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時，那麼自然區間内的所有數都可以湊出來了。
*/      

1 /*網上的AC代碼，我加了注解，注意把I64d改為lld*/
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<cmath>
 7 
 8 #define md
 9 #define ll long long
10 #define inf 1000000000000000LL
11 #define eps 1e-8
12 #define N 500010
13 using namespace std;
14 int q[N];
15 ll dis[N];
16 bool vis[N];
17 int mn,n;
18 int a[20];
19 void spfa()
20 {
21     int h=0,w=1,x,y; q[1]=0; vis[0]=1;/*第一個能湊出的數就是0*/ 
22     while (h!=w)
23     {
24         h++; if (h>mn+5) h=1; x=q[h];/*循環隊列，取出隊頭的數*/
25         for (int i=1;i<=n;i++)
26         {
27             y=(x+a[i])%mn;/*利用這個價值和其他價值組合所能達到的y，計算y的最小花費（因為隻有計算最小花費），才能用mn湊出更多的滿足區間條件的數*/
28             if (dis[y]>dis[x]+a[i])
29             {
30                 dis[y]=dis[x]+a[i];
31                 if (!vis[y])
32                 {
33                     vis[y]=1;
34                     w++; if (w>mn+5) w=1; q[w]=y;
35                 }
36             }
37         }
38         vis[x]=0;
39     }
40 }
41     
42 ll query(ll x)
43 {
44     ll ans=0;
45     for (int i=0;i<mn;i++)
46         if (dis[i]<=x) ans+=(x-dis[i])/mn+1; /*計算有多少個k滿足k*mn+i<=x，因為k>=0，是以還要加1*/
47     return ans;
48 }
49         
50 /*windows 用I64d linux 用lld*/    
51 int main()
52 {
53     mn=(1e9);
54     ll L,R;
55     scanf("%d%I64d%I64d",&n,&L,&R);
56     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，很好了解吧*/
57     for (int i=1;i<mn;i++) dis[i]=inf;/*設達到每個k*mn+i(i<mn)的最小花費，是以數組dis中隻有小于mn的i即可(*/
58     spfa();
59     printf("%I64d\n",query(R)-query(L-1));
60     return 0;
61 }      

1 /*
 2 首先，答案=ans(Bmax)-ans(Bmin-1)//利用差分
 3 找出a1到an中的最小值p，則如果可以構造出答案x，就可以構造出答案x+p
 4 是以我們隻需要對于每個q(0<=q<p)，計算出最小的k，使k*p+q能夠能夠被構造出來，那麼對于k’(k’>k) k’*p+q也能構造出來
 5 是以對于每個q建一個點，對于每個ai，從q向(q+ai)%p連一條長度為ai的邊，先跑一遍最短路，計算出得到每個q的最小花費，如果最小花費大于了Bmax，那麼沒有辦法湊出了。否則就計算可以湊出多少個。
 6 
 7 */
 8 #define N 15
 9 #define S 500010 //注意題目時5*1e5
10 #include<iostream>
11 using namespace std;
12 #include<cstdio>
13 #include<queue>
14 typedef long long ll;
15 ll L,R;
16 bool vis[S]={0};
17 int n,mn=(1<<31)-1,a[N];
18 ll dis[S];
19 void input()
20 {
21     cin>>n>>L>>R;
22     for(int i=1;i<=n;++i)
23     {
24         scanf("%d",&a[i]);
25         if(a[i]==0)
26         {
27             i--;n--;
28             continue;
29          } 
30         mn=min(mn,a[i]);
31     }
32 }
33 void spfa()
34 {
35     queue<int>Q;
36     Q.push(0);
37     vis[0]=true;
38     dis[0]=0;/*注意得到0的花費是0*/
39     int x,y;
40     while(!Q.empty())
41     {
42         x=Q.front();Q.pop();
43         vis[x]=false;
44         for(int i=1;i<=n;++i)
45         {
46             y=(x+a[i])%mn;
47             if(dis[y]>dis[x]+a[i])
48             {
49                 dis[y]=dis[x]+a[i];
50                 if(!vis[y])
51                 {
52                     vis[y]=true;
53                     Q.push(y);
54                 }
55             }
56         }
57     }
58 }
59 ll query(ll x)
60 {
61     ll ans=0;
62     for(int i=0;i<mn;++i)/*别忘了從0開始循環，因為湊出的是0，可以全部用mn來湊*/
63       if(dis[i]<=x) ans+=(x-dis[i])/mn+1;
64     return ans;
65 }
66 int main()
67 {
68     input();
69     for(int i=0;i<mn;++i)
70       dis[i]=100000000000000000LL;//當指派longlong的數時，要加字尾ll（大小寫都可以）才可以，否則會出錯的。 
71     spfa();
72     cout<<query(R)-query(L-1);
73     return 0;
74 }