题解：CF2066C Bitwise Slides

rubbishZZZ · 2025-02-21 17:48:32 · 题解

CF2066C Object Identification

题意：

• 给定一个数组 a_1, a_2, \dots, a_n，另外给定三个变量 P, Q, R，初始值均为零。

  你需要按顺序处理所有数字 a_1, a_2, \dots, a_n。在处理下一个 a_i 时，你必须执行以下三种操作中的恰好一种：

  • P \leftarrow P \oplus a_i
  • Q \leftarrow Q \oplus a_i
  • R \leftarrow R \oplus a_i

  其中，\oplus 表示按位异或操作。

  在执行操作时，必须遵循一个主要规则：每次操作后，P, Q, R 三个数必须不是彼此不同的。

  总共有 3^n 种方式来执行所有的 n 个操作。请计算有多少种方式不违反主要规则。由于答案可能非常大，请对 10^9 + 7 取模。

解法：

• 我们设 sum_i 表示 a_1\oplus a_2\oplus\cdots\oplus a_i，则在 i 时刻 P\oplus Q\oplus R=sum_i，且 P,Q,R 中有两个一样。那么一定是一个 sum_i 与两个相同的数，无序情况下形如 (x,x,sum_i)。

  那么 (x,x,sum_i) 由什么转移而来的？

  那么用 map 来维护 dp_{i,j} 表示考虑了前 i 个数，x=j 的方案数。

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <ctime>
#include <random>
#include <cassert>
#include <numeric>
#include <cmath>
#include <bitset>
#include <ext/pb_ds/assoc_container.hpp>
#define pii pair<int, int>
#define fi first
#define se second
#define MP make_pair
#define ep emplace
#define eb emplace_back
#define int long long
#define rep(i, j, k) for (int i = (j); i <= (k); i++)
#define per(i, j, k) for (int i = (j); i >= (k); i--)
typedef double db;
typedef long double ldb;
typedef long long ll;
//typedef __int128 lll;
typedef unsigned long long ull;
typedef unsigned int ui;
using namespace std;
using namespace __gnu_pbds;
bool Mbe;

//char buf[1<<20],*p1,*p2;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin), p1 == p2) ? 0 : *p1++)
int read() {
    int s = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') f ^= (c == '-'), c = getchar();
    while (c >= '0' && c <= '9') s = s * 10 + c - '0', c = getchar();
    return f ? s : -s;
}
template<typename T>void chkmax(T&x,const T&y){if(x<y)x=y;}
template<typename T>void chkmin(T&x,const T&y){if(x>y)x=y;}
//int fplus(int x,int y){return x+y>=mod?x+y-mod:x+y;}
//void Fplus(int&x,int y){x=fplus(x,y);}
//int fminus(int x,int y){return x-y<0?x+mod-y:x-y;}
//void Fminus(int&x,int y){x=fminus(x,y);}

const int mod=1e9+7,N=200005;
int n,a[N],ans;
map<int,int>mp;

bool Med;
signed main() {
    fprintf(stderr,"%.3lfMb\n",(&Mbe-&Med)/1024./1024.);
    for(int T=read();T--;){
        ans=0;
        map<int,int>().swap(mp);
        n=read();
        rep(i,1,n)a[i]=read();
        mp[0]=1;
        int x=0;
        rep(i,1,n){
            mp[x]=(mp[x]*3+mp[a[i]^x]*2)%mod;
            x^=a[i];
        }
        for(pii p:mp)ans=(ans+p.se)%mod;
        printf("%lld\n",ans);
    }
    return 0;
}