POI XIII Stage 3. Problem Crystals

Brief description:

给定一个 n 个元素的数组 {ai}, 问存在多少组 {xi, xi <= ai && 所有 xi 的 xor 和 等于 0}。。。 ( n <= 50 .. )

亦或和等于 0 和等于 k 的版本几乎没有区别,讨论前者。

这类题目的解法是从高到低按位分阶段组合 DP .. .
我们的目的是,在每轮的 DP 过后,这一位上所有至少 Skip 一位的组合,全部被计数,这样做之后,剩下的所有还没有被计数的情况(没有发生 Skip)就会形成一个结构相同的子问题 …

额,还没有定义 Skip …

我们讨论当前扫描的是最高位 … 对于那些在这一位上是 1 的元素,这些元素有两种决策:
分别 是取 1 和取 0,我们称那些含有 1 的元素,取 0 的决策为 折越 (Skip) …

那么对于当前第 i 位,扫描了 j 个数字,我们设计状态 f[0], f[1], f[2] 分别为
从未发生过 折越 、发生过奇数次 折越、和发生过偶数次 折越 且不包括 f[0]。

分类讨论 dp 。。。

#define c ((a[j] & _U(i)) + 1)
#define g (1 << i)
 
…
 
        REP(j, n){
            if (_1(a[j], i)) {
                int w1 = sum(f[0], pdt(f[2], g)), w2 = pdt(f[1], g); t ^= 1;
                MUL(f[0], c), MUL(f[1], c), MUL(f[2], c);
                INC(f[1], w1), INC(f[2], w2);
            }
            else {
                MUL(f[0], c), MUL(f[1], c), MUL(f[2], c);
            }
        }
 
…

之后,我们考虑含有 1 的个数的奇偶性,
如果含有奇数个1,那么我们前面所说没有发生过一次 折越 (Skip) 的情况就不会出现在计数方案中,因此直接跳出。
每一位的复杂度为 O(n) ,总的复杂度为 O(nb),b 表元素的二进制位数 … (最后边界处别忘了所有元素都为 0 的话也是一组解 .. .)


.
.

(另,推公式的过程中还有一个难点,具体的说来是这样,对于当前扫描到第 i 位,一个发生了 k 次 折越 的状态,是需要保证 (i, 0] 位上的亦或和为 0 的。
因为发生 折越 的位置之后的二进制位可以任意组合,所以如果固定了其中的任意 k-1 个元素的状态,总可以设置一种第 k 个元素的状态,使得 (i, 0] 位上的亦或和为 0,这也是组合 dp 可以奏效的依据。)

http://www.lydsy.com/JudgeOnline/problem.php?id=1442
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=384&problem=3102&mosmsg=Submission+received+with+ID+856655
http://main.edu.pl/en/archive/oi/13/kry
SRM 508 DIV 1 Level 2. YetAnotherORProblem
http://hi.baidu.com/%D2%BB%CE%BB%C1%E3/blog/item/603ee5b68bf283e630add144.html
http://blog.163.com/fjxmlhx@126/blog/static/144072841201022492458853/