显然数位DP。

dp[i][j]表示所有末尾为j的i位二进制数相邻位的数量和

初始状态dp[2][1]=1

从长度i-1转移到长度i就是在i-1位的末尾添上0或1，转移方程就是：

dp[i][0]=dp[i-1][0]+dp[i-1][1]

dp[i][1]=dp[i-1][0]+dp[i-1][1]+2i-2

预处理完后，就可以通过这个计算出[0,n]区间的数量和，还是感觉数位DP的这一步挺棘手的，具体问题具体分析吧。。

#include
#include
using namespace std;
long long d[][];
int main(){
d[][]=;
for(int i=; i<; ++i){ d[i][]=d[i-][]+d[i-][]; d[i][]=d[i-][]+d[i-][]+(<=; --i){
if((n>>i)&) res+=d[i][]+d[i][];
if(((n>>i)&) && ((n>>i+)&)) res+=(n&((1LL<<i+)-))-((<<i)|(<<i+))+;
}
printf("Case %d: %lld\n",cse,res);
}
return ;
}