[DP记录]AT2272 [ARC066B] Xor Sum

**题意** ： 给出正整数 $n$。 求出满足下列条件的数对 $(u,v)$ 的数目 ： - $u,v\in[0,n]∩\rm Z$ - 存在 $a,b\in \rm N$ 满足 $a{\ \rm xor\ }b=u,\ a+b=v$。 答案对 $10^9+7$ 取模。 $n\leq 10^{18}$ ，时限$\texttt{2s}$。 ------------ 由于异或是不进位的加法，故 $a{\ \rm xor\ }b\leq a+b$。 所以所有合法数对必然有 $u\leq v$ ，只需进一步限制 $v\leq n$ 即可。 记 $f_i$ 为 $v=i$ 时符合题意的 $u$ 的个数。答案即为 $\sum_{i=1}^nf_i$。 考虑利用递推求解 $f_v$。 边界 ： $f_0=1$。 - 若 $v$ 是奇数，则 $a,b$ 中必有且仅有一者为奇数。 去掉 $a,b$ 的最后一位，则相当于 $v\leftarrow (v-1)/2$。 此时 $f_v=f_{(v-1)/2}$。 - 若 $v$ 是正偶数，则 $a,b$ 或者全是偶数，或者全是奇数。 去掉 $a,b$ 的最后一位，则相当于 ： - （全偶） $v\leftarrow v/2$。 - （全奇） $v\leftarrow (v-2)/2$。 此时 $f_v=f_{v/2}+f_{(v-2)/2}$。 已经可以 $O(n)$ 求解各个 $f$。 记 $s_i=\sum_{j=1}^if_j$ ，目标是求出 $s_n$。 考虑 $s$ 的递推式 ： - $i$ 为偶数 $$ \begin{aligned} s_i&=f_0+\sum\limits_{i=0}^{n/2-1}f_{2i+1}+\sum\limits_{i=1}^{n/2}f_{2i}\\ &=f_0+\sum\limits_{i=0}^{n/2-1}f_{i}+\sum\limits_{i=1}^{n/2}f_{i}+f_{i-1}\\ &=2s_{n/2-1}+s_{n/2} \end{aligned} $$ - $i$ 为奇数（且 $i>1$） $$ \begin{aligned} s_i&=f_0+\sum\limits_{i=0}^{(n-1)/2}f_{2i+1}+\sum\limits_{i=1}^{(n-1)/2}f_{2i}\\ &=f_0+\sum\limits_{i=0}^{(n-1)/2}f_{i}+\sum\limits_{i=1}^{(n-1)/2}f_{i}+f_{i-1}\\ &=2s_{(n-1)/2}+s_{(n-1)/2-1} \end{aligned} $$ 记忆化搜索即可，可以证明复杂度为 $O\big({\rm poly}(\log n)\big)$。 ```cpp #include<algorithm> #include<cstdio> #include<map> #define ll long long using namespace std; const int mod=1000000007; map<ll,int> o; int dfs(ll n) { if (o.find(n)!=o.end())return o[n]; if (n<=1)return n+1; return o[n]=(n&1) ? (2ll*dfs(n/2)+dfs(n/2-1))%mod : (2ll*dfs(n/2-1)+dfs(n/2))%mod; } int main() { ll n;scanf("%lld",&n); printf("%lld",dfs(n)); return 0; } ```