P9387 巧克力

题面

见此

思路

$4k\oplus{4k+1}\oplus{4k+2}\oplus{4k+3}=0$

这样就可以快速处理出$x$的值。

我们设$f_{i,j,k=0/1,t=0/1}$表示我考虑了二进制的前$i$位$(0\sim{i})$，当前位将向下进位的值是$j,j\in{0\sim{n}}$，$k$表示$b$是否大于$0$：$true/false$，$t$表示前$i$位是否大于$n$，此时的方案数。

（$b$大于或等于$0$）

那就可以从低位到高位进行 DP 了，初始时$f_{-1,0,0,0}=1$

转移方程是：

$f_{i+1,y,O_b|t,0/1}+=f_{i,j,t,k}$

这里$y=\lfloor\frac{O_a+O_b+O_c+j}{2}\rfloor$。

$O_x$代表$x$的当前这一位的值，由于要满足$(a+b+c)\oplus{a}\oplus{c}=x$，因此设$z={O_a+O_b+O_c}\pmod{2}$，$z\oplus{O_a}\oplus{O_c}=O_x$。而这位的$O_a,O_b,O_c$分别枚举一下就好了，选出符合这个条件的进行转移。

$n$个二进制数加起来最多进$n-1$位，三个数最多进$2$位。

至于$\le{n}$，假如下一位小于$n$的下一位，那么就是小于
$n$，为$0$，假如下一位和$n$相同，那就继承上一个状态，因为还要接着比下去，如果下一位比$n$大，那就是大于，为$1$。

最后的答案就是$f_{60,0,1,0}$，因为$1e18$的二进制位数不会超过$60$位。