首页 > 其他分享 >ARC139F Many Xor Optimization Problems

ARC139F Many Xor Optimization Problems

时间:2022-10-23 00:00:44浏览次数:65  
标签:Xor Many Problems 异或 Optimization ARC139F

题意:给定 \(n,m\),求 \(n\) 个 \([0,2^m)\) 的数的最大异或和的和。

瞎扯:考虑线性基,考虑消元后的,显然唯一,最大异或和为基内所有数的异或和。考虑大小为 \(k\) 的基方案数为 \(\sum\limits_{i=0}^k (-1)^{k-i}\dbinom{k}{i} 2^{ni}=(2^n-1)^k\)。

考虑有多少大小为 \(k\) 的线性基,\(f_{i,j}=f_{i-1,j}+f_{i-1,j-1}2^{i-j}\)

标签:Xor,Many,Problems,异或,Optimization,ARC139F
From: https://www.cnblogs.com/syzf2222/p/16817658.html

相关文章