CF1770F Koxia and Sequence

妙妙题。

首先第一步，因为对于任意 $a_i=t$ 的情况数量是相等的，所以 $n$ 为偶数的情况的答案是 $0$，$n$ 为奇数我们只需要求 $a_1$ 的异或和即可。

考虑先满足 $+$ 的条件即 $\sum a_i=x$，再拆成每一位满足 $\operatorname{OR}$ 的限制即 $\operatorname{OR}a_i=y$。这是第一步。

第二步， $\operatorname{OR}a_i=y$ 的限制太死了，考虑容斥，设 $f(y)$ 为满足 $\operatorname{OR}a_i$ 为 $y$ 的子集的方案数，那么恰好满足 $\operatorname{OR}a_i$ 为 $y$ 的方案数为 $\displaystyle \sum_{y’\subseteq y}(-1)^{|y|-|y’|}f(y’)$，我们只关心奇偶性，直接写成 $\displaystyle \bigoplus_{y’\subseteq y} f(y’)$，对 $y’$ 进行限制即可。

第三步，钦定当前位为 $i$，设 $a_1=a_1’-2^i$，列出答案式子：

$$\text{ans}=\bigoplus_{\sum a_i=x-2^i}[a_1'\subseteq y'-2^i][a_2\subseteq y']\cdots[a_n\subseteq y']$$

第四步，子集的限制我们并不好合并，考虑 $\displaystyle \binom{x}{y}=[y\subseteq x]\pmod 2$，于是将子集限制全部替换为组合数得到：

$$\text{ans}=\bigoplus_{\sum a_i=x-2^i}\binom{y'-2^i}{a_1}\binom{y'}{a_2}\cdots\binom{y'}{a_n}\pmod 2$$

注意到 $\sum a_i=x-2^i$ 的限制，我们可以使用范德蒙德卷积公式直接处理，进一步得到：

$$\begin{align} \text{ans}&=\binom{ny'-2^i}{x-2^i}\pmod 2\notag\\ &=[x-2^i\subseteq ny'-2^i]\notag\\ \end{align}$$

于是直接枚举计算即可，时间复杂度为 $\mathcal O(y\log y)$。

Code

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int K=20;
ll n,x;
int y,ans;

int main()
{
    scanf("%lld %lld %d",&n,&x,&y);
    if(!(n&1))return puts("0"),0;
    ll now=0;
    for(int i=0;i<=y;now+=n,i++)
    {
        if((i&y)!=i)continue;
        for(int j=0;j<K;j++)
        {
            if(!(i>>j&1))continue;
            ll fir=now-(1<<j);
            ll sec=x-(1<<j);
            if(fir>=0&&sec>=0&&(sec&fir)==sec)ans^=1<<j;
        }
    }
    printf("%d\n",ans);
    return 0;
}