为什么A掉的人这么多没有写题解QAQ
首先我们选出最小的a，不妨设为a[1]，对于某个数x，先用最小的a来拼，使得x = a[1] * p + r (0 ≤ r < a[1])
然后是很神奇的地方：建图最短路！
对于每个模数r我们建一个点p
然后我们暴力枚举点u，再暴力枚举选择方式a[i]，令v = (u + a[i]) % a[1]，则u向v连边权值为(u + a[i]) / a[1]，意思是从方案中退掉这么多的a[1]再加上a[i]才能从u到v
于是我们从0开始跑单源最短路，0到每个点的最短路d表示至少要退掉这么多a[1]才能到达，也即当x = (d + k) * a[i] + r (0 ≤ k)时才可以做到
然后就没了QAQ，详情请见程序。。。
1 /************************************************************** 2 Problem: 2118 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:5228 ms 7 Memory:74848 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <cstring> 12 #include <algorithm> 13 #include <queue> 14 15 using namespace std; 16 typedef long long ll; 17 const int N = 4e5 + 5; 18 const int M = 5e6 + 5; 19 20 struct edge { 21 int next, to, v; 22 edge() {} 23 edge(int _n, int _t, int _v) : next(_n), to(_t), v(_v) {} 24 } e[M]; 25 26 int first[N], tot; 27 28 struct heap_node { 29 int v, to; 30 heap_node() {} 31 heap_node(int _v, int _to) : v(_v), to(_to) {} 32 33 inline bool operator < (const heap_node &a) const { 34 return v > a.v; 35 } 36 }; 37 38 int n; 39 ll mn, mx, ans; 40 int a[15], dis[N]; 41 priority_queue <heap_node> h; 42 43 inline void add_edge(int x, int y, int z) { 44 e[++tot] = edge(first[x], y, z), first[x] = tot; 45 } 46 47 inline void add_to_heap(const int p) { 48 static int x; 49 for (x = first[p]; x; x = e[x].next) 50 if (dis[e[x].to] == -1) 51 h.push(heap_node(e[x].v + dis[p], e[x].to)); 52 } 53 54 void Dijkstra() { 55 memset(dis, -1, sizeof(dis)); 56 while (!h.empty()) h.pop(); 57 dis[0] = 0, add_to_heap(0); 58 int p; 59 while (!h.empty()) { 60 if (dis[h.top().to] != -1) { 61 h.pop(); 62 continue; 63 } 64 p = h.top().to; 65 dis[p] = h.top().v; 66 h.pop(); 67 add_to_heap(p); 68 } 69 } 70 71 int main() { 72 int i, j; 73 scanf("%d%lld%lld", &n, &mn, &mx); 74 mn -= 1; 75 for (i = 1; i <= n; ++i) { 76 scanf("%d", a + i); 77 if (a[i] < a[1]) swap(a[i], a[1]); 78 } 79 for (i = 0; i < a[1]; ++i) 80 for (j = 2; j <= n; ++j) 81 add_edge(i, (i + a[j]) % a[1], (i + a[j]) / a[1]); 82 Dijkstra(); 83 for (i = 0; i < a[1]; ++i) { 84 if (dis[i] == -1) continue; 85 ans += max(0ll, (mx - i) / a[1] - max(0ll, max((mn - i) / a[1], (ll) dis[i] - 1))); 86 } 87 printf("%lld ", ans); 88 return 0; 89 }
(p.s. 不要问我为什么这么慢！我！也！不！知！道！)