【BZOJ 2118】 2118: 墨墨的等式 (最短路)

时间:2024-10-23 18:36:32

2118: 墨墨的等式

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。

Source

【分析】

  看了好久题解,感觉好机智啊。。

  题目可以理解成经典的背包问题。只是他问你的是[L,R]区间中有多少个容积是恰好可以装满的。

  然后这个范围很大啊,传统的暴力当然是行不通的了。

  考虑一个可以被拼出来的x,他里面可以包含ai也可以不包含ai。设x%ai=b(0<=b<ai)

  那么其实x+ai都可以被拼出来,显然。

  所以我们只要对于一个b,求出最小的可以拼出来的x,那么一直加ai也是可以的。

  直接把不同的b算出来的答案加起来就好了。

  要证明的话只要说明两个东西:

  1、不重复性,对于不同的可以拼出的x1,x2,如果他们%ai不同,那就不会算重复。

    如果他们%ai相同,也不会算重复【233我在搞笑?】

  2、不遗漏性,对于可以拼出来的x1,有一个模对应的b,那么肯定会算到嘛= =【233

  所以就这样搞笑的证明了??

  【想出来的人思路真的很妙【我根本看不出是最短路啊ORZ。。。

 #include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
#define LL long long
#define Maxm 7000100
#define Maxn 500010
#define INF 1000000000000LL int a[]; struct node
{
int x,y,next;
LL c;
}t[Maxm];int len=; // vector<int > e[Maxn],c[Maxn]; int first[Maxn]; void ins(int x,int y,LL c)
{
t[++len].x=x;t[len].y=y;t[len].c=c;
t[len].next=first[x];first[x]=len;
} LL dis[Maxn];
bool inq[Maxn];
queue<int > q;
void spfa()
{
int st=;
while(!q.empty()) q.pop();
memset(inq,,sizeof(inq));
// memset(dis,63,sizeof(dis));
for(int i=;i<a[];i++) dis[i]=INF;
q.push(st);dis[st]=;inq[st]=;
while(!q.empty())
{
int x=q.front();
for(int i=first[x];i;i=t[i].next)
{
int y=t[i].y;
// for(int i=0;i<e[x].size();i++)
// {
// int y=e[x][i];
if(dis[y]>dis[x]+t[i].c)
{
dis[y]=dis[x]+t[i].c;
// dis[y]=dis[x]+c[x][i];
while(!inq[y])
{
inq[y]=;
q.push(y);
}
}
}
inq[x]=;
q.pop();
}
} LL get_ans(LL x,LL y)
{
if(x<y) return ;
return (x-y)/a[]+;
} int main()
{
int n;
LL L,R;
scanf("%d%lld%lld",&n,&L,&R);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
sort(a+,a++n);
memset(first,,sizeof(first));
for(int i=;i<=n;i++)
for(int j=;j<a[];j++)
{
ins(j,(j+a[i])%a[],a[i]);
}
spfa();
LL ans=;
for(int i=;i<a[];i++)
ans+=get_ans(R,dis[i])-get_ans(L-,dis[i]);
printf("%lld\n",ans);
return ;
}

WA了很久竟然是spfa打错了。。。

2017-01-13 19:05:54