CF Round 812 F. Lost Array

F. Lost Array

I spent many hours fooling around yesterday, reading the wrong questions and reading the wrong code. Finally, I got out of the mess. I wrote a blog to record the mentality of nearly breaking the computer yesterday

Observe the mysterious code of others and find the following mysterious properties

For ordered column subset XOR, superset XOR and subset XOR, the sequence will be flipped

I, Taicai, don't know how to push intuitively. I can only verify by enumerating the contributions after reading the conclusions

for example

The procedure is as follows

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int P=10007;
 int main()
 {
     int n;scanf("%d",&n);
     vector<int> f(1<<n);
     for(int i=0;i<1<<n;++i)f[i]=rand()%P;

     printf("Initial sequence : ");
     for(auto v:f)printf("%d ",v);
     puts(" ");
     for(int i=0;i<n;++i)for(int j=0;j<1<<n;++j)
        if(j&1<<i)f[j]^=f[j^1<<i];

    for(int i=0;i<n;++i)for(int j=0;j<1<<n;++j)
        if(!(j&1<<i))f[j]^=f[j^1<<i];

    for(int i=0;i<n;++i)for(int j=0;j<1<<n;++j)
        if(j&1<<i)f[j]^=f[j^1<<i];

        printf("Terminal sequence : ");
     for(int i=0;i<1<<n;++i)printf("%d ",f[i]);
 }

The problem in the question can be converted into the (m-n,m] term of the known b through a series of transformations. Find the [0,n) term of a, and all [n,m] terms of a are zero, and perform subset XOR on a to get b

If we know the original sequence of b, we can get a only by one superset xor or+one subset xor, but unfortunately the first part of b is missing, so we have to explore other properties

It is not difficult to find that if [n,m] of a is all zero, then the superset xor of the original sequence b will make p[0,m-n] of b all zero.

Starting from the results, the sequence of superset XOR of the original sequence b is called c, and the sequence of subset XOR of c is called d.

Where the first [0,m-n+1] term of d is 0, and d is the result of XOR of c subset, and c[0]=d[0]=0, so c[1]=d[1]=0,c[2]=d[2]=0. So the first [0,m-n+1] terms of c are also 0.

Therefore, the result of superset XOR of incomplete sequence b is the same as that of the original sequence, so the

Of course, you can also write a program to try if you are not sure, such as

The code is as follows

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int P=10007;
 int main()
 {
     int n;scanf("%d",&n);
     vector<int> f(1<<n);
     for(int i=0;i<(1<<n)-10;++i)f[i]=rand()%P;

     printf("Initial sequence : ");
     for(auto v:f)printf("%d ",v);
     puts(" ");
     for(int i=0;i<n;++i)for(int j=0;j<1<<n;++j)
        if(j&1<<i)f[j]^=f[j^1<<i];

    for(int i=0;i<n;++i)for(int j=0;j<1<<n;++j)
        if(!(j&1<<i))f[j]^=f[j^1<<i];

  /*  for(int i=0;i<n;++i)for(int j=0;j<1<<n;++j)
        if(j&1<<i)f[j]^=f[j^1<<i];*/

        printf("C sequence : ");
     for(int i=0;i<1<<n;++i)printf("%d ",f[i]);
 }

So we are done. For this question, we have the following code

Of course, you don't need to write so much, you can write more succinctly

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
 
 int main()
 {
     int n;scanf("%d",&n);
     int pos=1,x=1;
     while(n>x)x<<=1,++pos;
     --x;
     vector<int> f(1<<20);
     for(int i=x;i>x-n;--i)
        scanf("%d",&f[i]);
     for(int i=0;i<pos;++i)
        for(int j=x-n+1;j<=x;++j)
        if(!(j&1<<i))f[j]^=f[j^1<<i];
     for(int i=0;i<pos;++i)
        for(int j=x-n+1;j<=x;++j)
        if(j&1<<i)f[j]^=f[j^1<<i];
 
     for(int i=x-n+1;i<=x;++i)printf("%d ",f[i]);
 }

Tags: C++ Algorithm

Posted by Sillysoft on Thu, 15 Sep 2022 21:16:40 +0300