CF1770F Koxia and Sequence
题目链接。
\(\text{difficulty}={\color{red}6},1\)。
\(\text{tags}=组合数学,子集反演,容斥原理,二进制\)。
神仙题。
首先进行观察。由于计算式与每个数在那个位置无关，所以每个位置都是相同的。
可以将 \(\bigoplus_a \bigoplus_{i=1}^n a_i\) 转化为 \(\bigoplus_{i=1}^n \bigoplus_a a_i\)，即对每个位置求出其贡献后将每个位置异或起来。由于每个位置都是相同的，所以当 \(n\) 为偶数时会贡献偶数次抵消掉了，答案为 \(0\)；当 \(n\) 为奇数时会贡献奇数次，那么我们只需要计算 \(a_1\) 的贡献即可。
注意到计算式中有 \(\text{OR}\)，考虑对 \(a_1\) 的每一位计算当前位为 \(1\) 的方案数。由于最终的答案为异或形式，所以只需要求出每一位答案的奇偶性即可。接下来讨论当 \(a_1\) 的第 \(i\) 位被钦定为 \(1\) 时的贡献，下面我们将 \(a_1\) 减掉 \(2^i\)。
由于有一个求和的限制和一个 \(\text{OR}\) 的限制，无法同时处理，考虑固定一个容斥另一个。
较为合理的做法是固定和然后容斥 \(\text{OR}\)，因为如果仅知道 \(\text{OR}\) 的信息来确定和较为困难。设 \(f_s\) 表示在 \(a_1\) 的第 \(i\) 位为 \(1\) 并且和满足条件的前提下，\(\text{OR}\) 恰好为 \(s\) 的方案数，\(g_s\) 表示在 \(a_1\) 的第 \(i\) 位为 \(1\) 并且和满足条件的前提下，\(\text{OR}\) 为 \(s\) 的子集的方案。
根据子集反演可以得到
\[f_s=\sum_{t\subseteq s} (-1)^{|s|-|t|}g_t \]由于我们只关心奇偶性，所以可以变形 \(f_s=\bigoplus_{t\subseteq s}g_t\)。
接下来考虑如何求出 \(g_s\)。我们将最暴力的式子列出来，可以得到（由于只关心奇偶性，所以可以直接用异或）
\[g_S=\bigoplus\limits_{\sum_{i=1}^n a_i=x-2^i} [a_1\subseteq (s-2^i)][a_2\subseteq s][a_3\subseteq s]\dots[a_n\subseteq s] \]接下来是最神仙的一步。考虑一个有关组合数奇偶性的公式 \(\binom{n}{m}\bmod 2=[m\subseteq n]\)，接下来我们考虑逆用这个公式。那么可以得到
\[g_s=\left(\sum_{\sum_{i=1}^n a_i=x-2^i} \binom{s-2^i}{a_1}\binom{s}{a_2}\binom{s}{a_3}\dots\binom{s}{a_n}\right)\bmod 2 \]发现中间是范德蒙德卷积的形式，直接化简得到
\[g_s=\binom{ns-2^i}{x-2^i}\bmod 2=[(x-2^i)\subseteq (ns-2^i)] \]此时一个 \(g_s\) 可以在 \(\mathcal{O}(1)\) 的时间复杂度内计算。回到原问题，我们需要 \(\mathcal{O}(\log y)\) 枚举一个选择的位，然后 \(\mathcal{O}(y)\) 枚举 \(s\) 并 \(\mathcal{O}(1)\) 计算 \(g_t\) 得到 \(f_s\)，则总时间复杂度 \(\mathcal{O}(y \log y)\)。
code
#include<bits/stdc++.h>
using namespace std;
namespace IO{
template<typename T>inline bool read(T &x){
x=0;
char ch=getchar();
bool flag=0,ret=0;
while(ch<'0'||ch>'9') flag=flag||(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(),ret=1;
x=flag?-x:x;
return ret;
}
template<typename T,typename ...Args>inline bool read(T& a,Args& ...args){
return read(a)&&read(args...);
}
template<typename T>void prt(T x){
if(x>9) prt(x/10);
putchar(x%10+'0');
}
template<typename T>inline void put(T x){
if(x<0) putchar('-'),x=-x;
prt(x);
}
template<typename T>inline void put(char ch,T x){
if(x<0) putchar('-'),x=-x;
prt(x);
putchar(ch);
}
template<typename T,typename ...Args>inline void put(T a,Args ...args){
put(a);
put(args...);
}
template<typename T,typename ...Args>inline void put(const char ch,T a,Args ...args){
put(ch,a);
put(ch,args...);
}
inline void put(string s){
for(int i=0,sz=s.length();i<sz;i++) putchar(s[i]);
}
inline void put(const char* s){
for(int i=0,sz=strlen(s);i<sz;i++) putchar(s[i]);
}
}
using namespace IO;
#define int long long
int n,X,Y,ans;
signed main(){
read(n,X,Y);
if(!(n&1)) return puts("0"),0;
for(int i=0;i<=20;i++){
if(!(Y>>i&1)) continue;
int res=0;
for(int s=0;s<(1<<20);s++)
if((s>>i&1)&&(Y&s)==s&&((n*s-(1ll<<i))&(X-(1ll<<i)))==(X-(1ll<<i))) res^=1;
ans|=res<<i;
}
put('\n',ans);
return 0;
}