专栏文章

题解：P12177 [蓝桥杯 2025 省 Python B] 异或和

MMeickol
P12177题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mip8e95n
此快照首次捕获于
2025/12/03 07:50
3 个月前
此快照最后确认于
2025/12/03 07:50
3 个月前
查看原文

二进制拆位 + 贡献计算 + 快写输出 int128

原式：
∑i=1n∑j=i+1n(ai⊕aj)×(j−i)\sum_{i=1}^{n} \sum_{j=i+1}^{n} (a_i \oplus a_j) \times (j - i)
等价于：
∑k=020(2k×∑i=1n∑j=i+1n(j−i)[ai,k≠aj,k])\sum\limits_{k=0}^{20} \Bigg( 2^k \times \sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n} (j-i)[a_{i, k} \not=a_{j, k}] \Bigg)
为了更贴合我们的习惯，我们调换一下 ii 和 jj 的大小关系：
∑k=020(2k×∑i=1n∑j=1i−1(i−j)[ai,k≠aj,k])\sum\limits_{k=0}^{20} \Bigg( 2^k \times \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{i-1} (i-j)[a_{i, k} \not=a_{j, k}] \Bigg)
不难发现可以使用贡献计算的方式解决。
用 cntk,0/1cnt_{k,0/1} 记录枚举到的前 ii 个数的二进制表示下第 kk 位为 0/10/1 的个数。
再用 sumk,0/1sum_{k,0/1} 记录枚举到的前 ii 个数的二进制表示下第 kk 位为 0/10/1 的下标总和。
设当前枚举到的第 ii 个数的二进制表示下第 kk 位为 bitbit。
那么问题就转化为：
∑k=020(2k×∑i=1n(cntk,bit⊕1×i−sumk,bit⊕1))\sum\limits_{k=0}^{20} \Bigg( 2^k \times \sum\limits_{i=1}^{n}(cnt_{k,bit \oplus 1} \times i - sum_{k,bit \oplus 1} )\Bigg)
由于 2k2^k 可以达到 220=1062^{20}=10^6 规模，任意的 (i,j)(i,j) 数对可以达到 n2=1010n^2=10^{10} 规模，而 i−ji-j 又可以达到 n=105n=10^5 规模。共 106×1010×105=102110^6 \times 10^{10} \times 10^5 = 10^{21} 规模，所以可能爆 long long，需要开 __int128。
Talkischeap , Showmethecode.\large \mathscr Talk \quad is \quad cheap \ , \ Show \quad me \quad the \quad code. CPP
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
typedef long long LL;
const int N=1e5+5;
LL n;
LL a[N];
LL cnt[22][2],sum[22][2];
inline void write(__int128 x){
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
void solve(){
	cin>>n;
	rep(i,1,n) cin>>a[i];
	__int128 ans=0;
	per(k,20,0){
		rep(i,1,n){
			int bit=(a[i]>>k)&1;
			ans+=(1LL<<k)*(cnt[k][bit^1]*i-sum[k][bit^1]);
			cnt[k][bit]++,sum[k][bit]+=i;
		}
	}
	write(ans);
}

评论

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

正在加载评论...