【异或计数】

【问题描述】

给定长度为n的非负整数序列a,问有多少个长度为n的非负整数序列b,满足:

①bi≤ai

②b1^b2^b3^……bn=a1^a2^a3^……^an

答案对1000000009取模

【输入格式】

第一行一个正整数n

第二行n个非负整数ai

【输出格式】

输出一个数字,表示答案。

【样例输入】

4

1 2 3 4

【样例输出】

6

【数据范围】

1≤n≤10^5,ai≤2^30

题目来源:Codechef AMXOR

以下是某大神题解


 

这个题目有两个限制,一个是xor和相等,第二个是小于等于。

我们先分析第二个限制,我们从低位往高位考虑,对于每一个方案,跳过那些完全相等的位,肯定有一个位它上限为1,但方案中选为0

比如上限是111,100,011。方案是101,100,001,对于最高位他们都是相等的,到了第二位才开始严格小于。

当一个数有一位上限为1但实际为0时,显然低位是可以随便乱选的,怎么选都不会超过原上限。

由于这个低位存在一个可以乱选的数x,所以我们可以其它数乱选,最后x的低位选一个恰当的使得满足低位xor和相等,于是第二个限制就没了。

总结一下就是每一位DP,dp[i][j][k]表示考虑了前i个数,当前xor和为j,是否有一个数已经小于上限了(k=1表示有数小于上限,0表示没有)。

设当前考虑在第p位:

I 若a[i+1]这一位为1 则dp[i+1][j^1][k]=dp[i][j][k]*((a[i+1]&(2^(p-1)-1)+1)

dp[i+1][j][1]=dp[i][j][k]*(2^p-1)

II 若a[i+1]这一位为0

dp[i+1][j][k]=dp[i][j][k]*((a[i+1]&(2^(p-1)-1))+1)

最后把dp[n][sum][1]/2^(p-1)累加进答案即可。

时间复杂度:O(nlog(ai))


 

感觉好难理解……,总之就是我们枚举这个不会超过原上限的数是在那一位出现的,然后第i个数如果它就是那个数(前提它的那一位是1)那么它后面的数随便乱选有2^p次方种选法,不然有(a[i]+1)种选法比如0111第1位是0的话,后面不能乱选,范围是000~111,当然a[i]是在减掉0*(1<<3)的情况下计数的,如果到它之前就已经有数没有限制了那直接就是有2^p种选法,总之那一位是1的话就把1 0的情况算一遍然后把那一位置0 如果那一位是0就直接转移。其实那(a[i]+1)种选法在当前情况下不一定成立的,但是最后一定有一种满足条件的情况(即乱选的数x)能让这(a[i]+1)种情况都成立。答案除2^(p-1)是因为我们考虑n个数每个数都能这样转移,但总有一个数要成为那个x,即那个数只有成为x一种选法,所以把多算的2^p-1除掉。

另外,最后的答案要+1,因为我们没有考虑所有位都没有那个x的情况。

啊啊感觉脑子好混乱先碎觉去了……

下面是代码:

 

 

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*