BZOJ3687: 简单题(dp+bitset)

Description

小呆开始研究集合论了,他提出了关于一个数集四个问题: 1.子集的异或和的算术和。 2.子集的异或和的异或和。 3.子集的算术和的算术和。 4.子集的算术和的异或和。     目前为止,小呆已经解决了前三个问题,还剩下最后一个问题还没有解决,他决定把 这个问题交给你,未来的集训队队员来实现。

Input

第一行,一个整数n。 第二行,n个正整数,表示01,a2….,。

Output

 一行,包含一个整数,表示所有子集和的异或和。

Sample Input

2 1 3

Sample Output

6

HINT

【样例解释】   6=1 异或 3 异或 (1+3) 【数据规模与约定】 ai >0,1<n<1000,∑ai≤2000000。 另外,不保证集合中的数满足互异性,即有可能出现Ai= Aj且i不等于J

Source

打死也想不出来系列QWQ...

感觉自己的思维还是太僵化了,看到数列问题就开始想怎么优化枚举子集

但是很显然这种子集问题是不可能通过枚举子集来实现的,

正解:

首先我们要把问题转化到值域上去考虑

设f[i]表示子集和为i的方案,那么加入一个数x,所有的f[i]+=f[i-1]

考虑到最后的异或操作,因此我们只维护方案的奇偶性即可

这样的话用一个bitset就可以了

bitset中的^,实际上就是\%2

#include<cstdio>
#include<iostream>
#include<bitset>
#include<cstring>
using namespace std;
int N;
bitset<2000001>bit;
int main()
{
    scanf("%d",&N);
    bit[0]=1;
    while(N--)
    {
        int x;
        scanf("%d",&x);
        bit^=bit<<x;
    }
    int ans=0;
    for(int i=2000000;i>=0;i--)
        if(bit[i]==1) 
            ans^=i;
    printf("%d",ans);
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏乐百川的学习频道

一个余数问题的思考

刚刚在贴吧上看到一个很简单的算法小问题,顺便看到了很多人不同的思路。我觉得很有意思,所以也来研究一下。 问题如下: 一筐鸡蛋: 1个1个拿,正好拿完。...

20990
来自专栏Android知识点总结

关于正整数、质数与公因数及哥德巴赫猜想

15230
来自专栏zaking's

js算法初窥05(算法模式02-动态规划与贪心算法)

22530
来自专栏人工智能

每个AI程序员都应该知道的基础数论

-欢迎 这篇文章讨论了数论中每个程序员都应该知道的几个重要概念。本文的内容既不是对数论的入门介绍,也不是针对数论中任何特定算法的讨论,而只是想要做为数论的一篇参...

23470
来自专栏Duncan's Blog

回溯法笔记

为了应用回溯法,所要求的解必须能表示成一个n-元组(x1,x2,…,xn),其中xi是取自某个有穷集Si。通常,所求解的问题需要求取一个使某一规范函数P(x1,...

11320
来自专栏数据结构与算法

《具体数学》学习笔记

26350
来自专栏程序员宝库

LCS 算法:Javascript 最长公共子序列

作者:司徒正美 链接:https://segmentfault.com/a/1190000012864957 最长公共子序列(Longest Common Su...

634100
来自专栏机器人网

机器学习中基本的数学符号是什么?

本文介绍了机器学习中的基本数学符号。具体来说有算数符号,包括各种乘法、指数、平方根以及对数;数列和集合符号,包括索引、累加以及集合关系。此外,本文还给出了 5 ...

80560
来自专栏ml

错排公式

错排公式 百科名片 pala提出的问题: 十本不同的书放在书架上。现重新摆放,使每本书都不在原来放的位置。有几种摆法? 这个问题推广一下,就是错排问题: n个有...

41990
来自专栏逸鹏说道

码农眼中的数学之~数学基础

1维直线、2维平面(长宽)、3维空间(长宽高 | xyz轴)、4维时空(xyz轴+时间轴)

13430

扫码关注云+社区

领取腾讯云代金券