[BZOJ2118/Luogu2371][国家集训队]墨墨的等式

题目链接：

BZOJ2118

Luogu2371

数论(×

背包(×

暴搜(×

结论(×

图论(√

惊 不 惊 喜 意 不 意 外

显然，答案可以转化为(Ans[1,B_{Max}]-Ans[1,B_{Min}-1])，现在思考怎么计算(Ans[1,Lim])

首先，若能够组成(k*a_i+x(0le x<a_i,kinmathbb{N}))，那么(l*a_i+x(l>k))也可以组成。

若能对每一个(x)求出最小的(k*a_i+x)，那么就可以轻松地计算有多少(l)满足(l*a_i+xle Lim)。

怎么计算？Dijkstra！

建(0sim a_i-1)这(a_i)个点，表示对应(x)下最小的(k*a_i+x)，在剩余系跑一遍最短路即可。

(a_i)当然选最小的那个啊~~

时间复杂度 (O(na_ilog_2(na_i)))

代码：

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long ll;

int n,a[15],Mina=1e9;
ll BMin,BMax,Dis[500005];
struct Rec
{
	int p;
	ll d;
	inline bool operator<(const Rec &o)const
	{return d>o.d;}
};

void Dijkstra()
{
	std::priority_queue<Rec> q;
	memset(Dis,0x3f,sizeof Dis);
	q.push((Rec){0,Dis[0]=0});
	while(!q.empty())
	{
		int x=q.top().p;
		ll d=q.top().d;
		q.pop();
		if(d!=Dis[x])continue;
		for(int i=1,y;i<=n;++i)
			if(Dis[y=(x+a[i])%Mina]>d+a[i])
				q.push((Rec){y,Dis[y]=d+a[i]});
	}
}

ll Query(const ll x)
{
	ll Res=0;
	for(int i=0;i<Mina;++i)
		if(Dis[i]<=x)
			Res+=(x-Dis[i])/Mina+1;
	return Res;
}

int main()
{
	scanf("%d%lld%lld",&n,&BMin,&BMax);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
		if(!a[i])--i,--n;//小心ai为0的情况
		else Mina=std::min(Mina,a[i]);
	}
	Dijkstra();
	printf("%lld
",Query(BMax)-Query(BMin-1));
	return 0;
}