{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','https://www.xiaopingtou.cn//data/attach/topic/topicKPo7gB.jpg', '推荐 jobszheng5 的文章《[CodeForces 577B]Modulo Sum[实现][数学]》','https://www.xiaopingtou.net/article-59697.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}
0条评论
题目链接：[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;
}