YJQQQAQ's Blog

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <iostream>
using namespace std;

int n;
long long L,R;

const int MAXN = 500010;
int a[MAXN];
long long dis[MAXN];
bool inq[MAXN];
queue<int> q;
void spfa() {
	memset(dis,-1,sizeof dis);
	dis[0] = 0;
	q.push(0);
	inq[0] = 1;
	while (q.size()) {
		int cur = q.front();
		q.pop();
		inq[cur] = 0;
		for (int i=1;i<n;i++) {
			int pr = a[i];
			int to = (cur + pr) ;
			if (to >= a[n]) to -= a[n];
			if (dis[to] < 0 || dis[to] > dis[cur] + a[i]) {
				dis[to] = dis[cur] + a[i];
				if (!inq[to]) {
					inq[to] = 1;
					q.push(to);
				}
			}
		}
	}
}

long long  calc(long long x) {
	long long ret = 0;
	for (int i=0;i<a[n];i++) {
		if (dis[i] >= 0) {
			if (dis[i] > x) continue;
			ret += (x - dis[i]) / a[n] + 1;
		}
	}
	return ret;
}


int main() {
#ifdef YJQ_LOCAL
	freopen(".in","r",stdin);
#endif
	cin>>n>>L>>R;
	for (int i=1;i<=n;i++) {
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	spfa();
	cout<<calc(R) - calc(L - 1)<<endl;
}
 

题意：给定序列长为$N$的序列$X_i$，问在$[L,R]$中有多少值$V$可以被表示为$\sum_{i=1}^{N}{A_i \times X_i}$，其中$0 \leq A_i$且$A_i$为整数

思路：任取一个$X_p$,看用剩下的值，对于每一个$X_p$的余数，最小的可以达到的值是多少，那么对于任意比这个数大，且与这个数对于$X_p$同余的数都可以在此基础上，加上若干个$X_p$得到，前者是一个最短路的模型，统计答案的时候随便就水过了，注意long long