[CodeForces 577B]Modulo Sum[实现][数学]

2019-04-14 22:14发布

站内文章 / 模拟电子
11086 0 1461
题目链接：[CodeForces 577B]Modulo Sum[实现][数学] 题意分析： 给出n个数，再给出一个数m。问给出的n个数中，任意组合，是否存在组合出来和能被m整除。 解题思路： 进一步说：题目就是问：在所有这些数能得到的组合中，是否存在和使得其被m整除。显然，这些组合出来的和取余后不大于m，这里面存在着大量重复。所以我们可以用一个数组标记这个和是否出现过，如果没出现就放入vector数组，然后每次更新这个vector数组。 整个复杂度1e9。不过不会到达，原因是n>m时，答案一定存在，所以总复杂度应该是m^2。 具体理由如下： 正如前面所说，取余之后的数不大于m，当存在n>m个数时，考虑从第一个数字开始的连续和，不断地去与m取余，必定有一次会出现取余后的结果之前出现过。因为：假设每次新增一个数之后的连续和取余之后的数都是新的，那么至多m次之后就会出现之前出现过的连续和，设第一次出现的连续区间为[0,first]第二次出现的区间为[0,second]。那么必然有：(sum(0,first) + sum(first,second))%m = sum(0,first) % m + sum(first, second) %m = sum(0, second)。 因为sum(0,first) == sum(0, second)， 所以sum(first,second) % m = 0。好啦，证毕。 个人感受： 弱渣昨天那场跪惨了。感觉能力还是不足。数学是会呼吸的痛。 具体代码如下： #include #include #include #include using namespace std; const int MAXN = 1e3 + 111; int a, n, m, sum[MAXN]; bool flag = 0, vis[MAXN]; int main() { scanf("%d%d", &n, &m); vector sum; for (int i = 0; i < n; ++i) { scanf("%d", &a); a %= m; int len = sum.size(); for (int j = 0; j < len; ++j) // 更新vecotr数组 { int newSum = (sum[j] + a) % m; if (newSum == 0) { flag = 1; goto ed; } if (!vis[newSum]) { sum.push_back(newSum); vis[newSum] = 1; } } if (!vis[a]) // 别忘了要把这个数本身放进去 { if (a == 0) { flag = 1; break; } sum.push_back(a); vis[a] = 1; } } ed: if (flag) printf("YES "); else printf("NO "); return 0; }

热门文章