2023.8.10 练习

ARC065F

非常抽象。

ARC066D

我们知道 \(a+b=a\space xor \space b+2(a\wedge b)\)
考虑到若 \(u=a \space xor \space b,v=a+b\)
那么 \(v\ge u\).
我们只要统计所有 \(v\)，\((v,u)\) 的个数求和即可。
注意到若 \((u,v)\) 合法，那么 \((2u,2v)\)、\((2u,2v+2)\)、\((2u+1,2v+1)\) 合法。
记 \(f(n)\) 表示 \(v=n\) 时合法数对，则 \(f(n)=f(n/2)+[x是偶数]f(n/2-1)\).
答案是 \(F(n)=\sum_{0\le i\le n}f(n)\).
则 \(F(n)=\sum_{0\le i\le n}f(n/2)+\sum_{1\le i\le n}[i是偶数]f(n/2-1)\)
\(F(n)=[n是偶数] f(n/2)+2F((n-1)/2)+F(n/2-1)\)
\(F(n)=F(n/2)+F((n-1)/2)+F(n/2-1)\).
\(F(0)=1\).