C. 【UNR #2】黎明前的巧克力

题解:

不会FWT,只能水40分了

首先,要观察出的性质就是:

选出的集合要满足所有数亦或等于0,而在其中任选子集都可以满足条件,答案就等于sigma(2^size(s))

这样dp一波显然就可以O(na)了(由性质可知转移到新状态*2)

然后考虑数很少的

发现同一个数是奇数就是ai偶数就是0

所以仍旧这么dp一下 也就是转移的时候乘(2^1+2^3+2^5....) 不变的同理

上一篇:N-Gram


下一篇:Jquery Mobile转场特效之slide | 小小iPhone开发