专栏文章

题解：CF2066C Bitwise Slides

rrubbishZZZ
CF2066C题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miq7dgki
此快照首次捕获于
2025/12/04 00:09
3 个月前
此快照最后确认于
2025/12/04 00:09
3 个月前
查看原文

CF2066C Object Identification

题意：

  • 给定一个数组 a1,a2,…,ana_1, a_2, \dots, a_n，另外给定三个变量 P,Q,RP, Q, R，初始值均为零。
    你需要按顺序处理所有数字 a1,a2,…,ana_1, a_2, \dots, a_n。在处理下一个 aia_i 时，你必须执行以下三种操作中的恰好一种：
    • P←P⊕aiP \leftarrow P \oplus a_i
    • Q←Q⊕aiQ \leftarrow Q \oplus a_i
    • R←R⊕aiR \leftarrow R \oplus a_i
    其中，⊕\oplus 表示按位异或操作。
    在执行操作时，必须遵循一个主要规则：每次操作后，P,Q,RP, Q, R 三个数必须不是彼此不同的。
    总共有 3n3^n 种方式来执行所有的 nn 个操作。请计算有多少种方式不违反主要规则。由于答案可能非常大，请对 109+710^9 + 7 取模。

解法：

  • 我们设 sumisum_i 表示 a1⊕a2⊕⋯⊕aia_1\oplus a_2\oplus\cdots\oplus a_i，则在 ii 时刻 P⊕Q⊕R=sumiP\oplus Q\oplus R=sum_i，且 P,Q,RP,Q,R 中有两个一样。那么一定是一个 sumisum_i 与两个相同的数，无序情况下形如 (x,x,sumi)(x,x,sum_i)。
    那么 (x,x,sumi)(x,x,sum_i) 由什么转移而来的？
    1. (x,x,sumi)←(sumi−1,sumi−1,sumi−1⊕ai),x=sumi−1(x,x,sum_i)\leftarrow (sum_{i-1},sum_{i-1},sum_{i-1}\oplus a_i),x=sum_{i-1}。系数为 33。
    2. (x,x,sumi)←(sumi,sumi⊕ai,sumi−1),x=sumi−1(x,x,sum_i)\leftarrow(sum_i,sum_i\oplus a_i,sum_{i-1}),x=sum_{i-1}。系数为 22。
    那么用 map 来维护 dpi,jdp_{i,j} 表示考虑了前 ii 个数，x=jx=j 的方案数。

代码：

CPP
#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;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...