bzoj2118（加法原理）（墨墨的等式）

题目大意：给定n个物品，每个物品有一个非负价值，问[L,R]区间内有多少价值可以被凑出来。

题意网上一大片，具体求解过程是利用了加法原理，将各个模数拥有的个数之和相加。

就是说随机取一个数a[k]，那么就是对于每个模数，通过转移的方式求出到达每个模数的最短路，将每个模数

0-(a[k]-1)之间的数连每个对应的a[j] (%a[k])意义下，花费为路的长度，这样就好了，最后前缀和相减求答案。

 #include<cmath>

 #include<queue>

 #include<cstdio>

 #include<vector>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 typedef pair<ll,int>fzy;

 const ll INF=1e16+;

 int n;

 int a[];

 int cnt,head[],next[],rea[],val[];

 ll ans=,l,r,dis[];

 bool boo[];

 struct cmp

 {

     bool operator()(fzy x,fzy y)

     {

         return x.first>y.first;

     }

 };

 priority_queue<fzy,vector<fzy>,cmp>q;

 void add(int u,int v,int fee)

 {

     cnt++;

     next[cnt]=head[u];

     head[u]=cnt;

     rea[cnt]=v;

     val[cnt]=fee;

 }

 void Dijkstra()

 {

     for (int i=;i<a[];i++)

         dis[i]=INF,boo[i]=;

     dis[]=;

     q.push(make_pair(,));

     while (!q.empty())

     {

         fzy now=q.top();

         q.pop();

         int u=now.second;

         if (boo[u]) continue;boo[u]=;

         for (int i=head[u];i!=-;i=next[i])

         {

             int v=rea[i],fee=val[i];

             if (dis[v]>dis[u]+fee)

             {

                 dis[v]=dis[u]+fee;

                 q.push(make_pair(dis[v],v));

             }

         }

     }

 }

 int main()

 {

     memset(head,-,sizeof(head));

     scanf("%d%lld%lld",&n,&l,&r);

     for (int i=;i<=n;i++)

         scanf("%d",&a[i]);

     sort(a+,a+n+);

     for (int i=;i<a[];i++)

         for (int j=;j<=n;j++)

             add(i,(a[j]+i)%a[],a[j]);

     Dijkstra();

     for (int i=;i<a[];i++)

     if (dis[i]<=r)

     {

         ll x=max((ll),(l-dis[i])/a[]),y=(ll)(r-dis[i])/a[];

         if (x*a[]+dis[i]<l) x++;

         if (y*a[]+dis[i]>r) y--;

         ans+=y-x+;

     }

     printf("%lld\n",ans);

 }