[暴力][分块][思维] CF 1030E Vasya and Good Sequences

题意如果一个序列中[l,r]里面的数,可以通过调整每个数的二进制位使得其异或和为0,那么这个[l,r]对就是good的,然后求有多少个这种[l,r]对,序列长度3e5。

一开始想dp,又是分位又是奇偶的,始终没搞出来。看了官方题解才发现判定一个[l,r]段是否为goog的充分必要条件只有两个,首先设bi为ai的二进制表示中的1的个数,则充要条件为:

① Σbi(l<=i<=r) 为偶数

② max(bi)<=Σbi(i!=index(max(bi))

第一个条件很容易理解:每次异或消掉的一定是一对1,如果最后能全消掉那么一定是偶数个1。第二个条件,一群数字异或之后能得到的最多1的数量是  min(他们的和,64),这是因为可以任意摆布每个数字里每个1的位置。然后要消掉某个数,那一定得其他数字能达到的最多1起码不小于这个数字的1个数,然后我们发现只要拥有最多1的数字满足这个限制,那剩下的一定满足这个限制(剩下的bi肯定比最大的小,而“其他的和”一定又比之前的大,所以最大的满足的话其他一定满足。

但是这样的话,假使使用遍历左端点然后求右端点个数的策略,需要同时考虑两个条件就会使得复杂度为O(n²),但是注意到每一个数字最少有一个1(1<=ai),那么当段的长度大于64(实际61就够了)的时候,最大的那个数字的1的数量一定小于其他所有数bi的和,因为最大的那个再大也大不过64,其他的和由于每个至少为1所以至少不小于64,所以第二个条件这时候是肯定满足的。这也就意味着我们可以暴力判别长度为64范围内的不合法得情况。

再来看第一个条件,其实可以预处理出来一个后缀和cnt[2][i],表示从当前i位置往后算,有多少个端点加到n的bi和为奇数/偶数,这样的话,只要根据当前的bi是奇数还是偶数选择加哪个就可以了。

实现时需要注意的细节是,由于cnt这个东西保存的某种意义上是左闭区间,所以从后往前算当前一点的时候只能算cnt[i+1]的,这个地方wa了。然后也是由于这个性质,需要给cnt[0][n+1]赋值为1.(如果不这样就会出现明明为偶数却什么都没加的情况)

 

#include
#include
#include
#include
#include
#include
#include

using namespace std;
typedef long long LL;
const int maxn=3e5+5;
const int mod=1e9+7;

LL gcd(LL a,LL b)
{
    return !b?a:gcd(b,a%b);
}

int  b[maxn];
int cnt[maxn][2];
LL psum[maxn];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    LL tmp;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>tmp;
        b[i]=__builtin_popcountll(tmp);
    }
    cnt[n+1][0]=1;//right edge
    LL res=0;
    for (int i=n; i>0; i--)
    {
        psum[i]=psum[i+1]+b[i];
        int dl=0,ts=0,ms=0;
        for (int j=i; j<=n&&j(ts-ms))//error1
                dl++;
        }
        res-=dl;
        cnt[i][0]=cnt[i+1][0];
        cnt[i][1]=cnt[i+1][1];
        if(psum[i]%2)
            cnt[i][1]++;
        else
            cnt[i][0]++;
        /
        if(psum[i]%2)
            res+=cnt[i+1][1];
        else
            res+=cnt[i+1][0];
    }
    cout<
	

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据