最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

Codeforces Good Bye 2022 CF 1770 F Koxia and Sequence 题解

来源：博客园


(资料图)

题目链接

注意题目要求的是所有好序列的所有元素的XOR之和的XOR之和。我一开始以为是所有XOR之和的加法和导致不知道官方题解在讲什么。

假设我们枚举一个位置\(1\le i\le n\)和一个数值\(v\)，统计第i个位置为v的好序列的个数，如果个数为奇数就可以把最终答案异或上v。由于对于同一个v和不同的i，这个个数都相同，所以n为偶数的时候最终答案是0。要先把这个特判掉，不然影响后面思考。n为奇数的情况，其实我们就只要枚举所有v，求出\(a_1=v\)的好序列的个数，如果是奇数就把答案异或上v就行了。把数值的每一位拆开进一步转化成这样：枚举一个bit i(\(0\le i\le19\))，求出\(a_1\)的二进制第i位为1的好序列的个数，如果个数是奇数则最终答案的第i位为1。观察可以发现这个问题形式与之前的那个等价。

我们先枚举i。一个好的序列要满足所有元素的或=y，要求刚好=y是很难计算的，不如用容斥：定义\(f_s\)表示所有元素的或是s的子集(可以=s)，且和为x，同时满足\(a_1\)的第i位为1的好序列个数。那么或刚好=y的好序列数量=\(\sum_{s\subseteq y}f_s(-1)^{|s\ xor\ y|}\)。令\(g_s=f_s\ mod \ 2\)，那么或刚好=y的好序列数量奇偶性=\(\bigoplus_{s\subseteq y}g_s\)，其中\(\bigoplus\)表示异或和。

当确定了i和s时，\(g_s\)其实是好算的。先看不要求\(a_1\)的第i位为1的情况，\(g_s=(\sum_{t_1,t_2\cdots t_n,\sum_t=x} \prod_{i=1}^n [t_i\&s=t_i])mod\ 2\)。有一个关于组合数的结论，\([m\&n=m]=\binom nm \ mod\ 2\)，也就是\(\binom nm\)为奇数的充要条件是\(m\)为\(n\)的子集。所以\(g_s=(\sum_{t_1,t_2\cdots t_n,\sum_t=x} \prod_{i=1}^n \binom{s}{t_i}\ mod\ 2)mod\ 2=\binom{ns}{x}\ mod\ 2\)。加上要求\(a_1\)的第i位为1的条件，其实也只要改成要求\(s\)的第i位为1，然后\(g_s=\binom{ns-2^i}{x-2^i}\ mod\ 2\)就行了。

枚举所有i和s然后算出所有\(g_s\)就能求出最终答案了。总时间复杂度\(O(ylogy)\)。

点击查看代码
#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){  #ifdef LGS  freopen("in.txt","r",stdin);  freopen("out.txt","w",stdout);  #endif}void termin(){  #ifdef LGS  std::cout<<"\n\nEXECUTION TERMINATED";  #endif  exit(0);}using namespace std;LL n,x,y;int main(){  fileio();  cin>>n>>x>>y;  if(n%2==0){puts("0");return 0;}  LL ans=0;  rep(i,20)  {    LL res=0;    for(LL sub=y;sub>0;sub=(sub-1)&y) if(sub&(1<

关键词： 题目要求 充要条件 时间复杂度