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 <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back

void 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<<i))
    {
      LL up=n*sub-(1LL<<i),dn=x-(1LL<<i);
      if(up<0||dn<0) continue;
      if((up&dn)==dn) res^=1;
    }
    if(res) ans|=(1<<i);
  }
  cout<<ans<<endl;

  termin();
}