题意

给出\(n,a_i,B_{min},B_{max}\)，求使得\(a_1x_1+a_2x_2+...+a_nx_n=B\)存在一组非负整数解的\(B\in[B_{min},B_{max}]\)的数量。

\(n\le12,0\le a_i \le 5*10^5,1\le B_{min}\le B_{max}\le 10^{12}\)

sol

和之前那个Luogu3403跳楼机差不多啊。

无非就是拿\(a_i\)的最小值来当模数就好了。

理论上是需要去掉\(a_i=0\)的，然而直接写并没有\(WA\)。所以不要想着手造一组数据把我的代码hack掉

code

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

using namespace std;

#define ll long long

#define pli pair<ll,int>

#define mk make_pair

const int N = 5e5+5;

int n,a[12],to[N*12],nxt[N*12],ww[N*12],head[N],cnt,vis[N];

ll L,R,f[N],ans;

priority_queue<pli,vector<pli>,greater<pli> >Q;

void link(int u,int v,int w)

{

	to[++cnt]=v;nxt[cnt]=head[u];ww[cnt]=w;

	head[u]=cnt;

}

void Dijkstra()

{

	memset(f,63,sizeof(f));

	f[0]=0;Q.push(mk(0,0));

	while (!Q.empty())

	{

		int u=Q.top().second;Q.pop();

		if (vis[u]) continue;vis[u]=1;

		for (int e=head[u];e;e=nxt[e])

			if (f[to[e]]>f[u]+ww[e])

				f[to[e]]=f[u]+ww[e],Q.push(mk(f[to[e]],to[e]));

	}

}

int main()

{

	scanf("%d%lld%lld",&n,&L,&R);L--;

	for (int i=0;i<n;++i) scanf("%d",&a[i]);

	sort(a,a+n);

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

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

			link(i,(i+a[j])%a[0],a[j]);

	Dijkstra();

	for (int i=0;i<a[0];++i) if (f[i]<=R) ans+=(R-f[i])/a[0]+1;

	for (int i=0;i<a[0];++i) if (f[i]<=L) ans-=(L-f[i])/a[0]+1;

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

	return 0;

}

巴特西

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

题意

sol

code

最新文章

热门文章