原题大意

n维哈密尔顿超立方体

想知道a到b之间的顶点数,1 <= n <= 60;a,b都出现在n位格雷码中;

算法分析

求出两个格雷码对应的二进制数的十进制表示
做差即可。

有关格雷码的模板：

1. 二进制 -> Gray

LL to_gray(LL x)
{
    return x ^= (x>>1);//返回结果为Gray码的十进制表示。
}

2. Gray-二进制

LL to_bin(LL x)
{
    LL y = x;
    while(x>>=1)
    {
        y ^= x;
    }
    return y;
}

3. 构造长度为n的格雷码

vector<int> G;
for(int i=0;i<(1<<n);i++)
{
    G.push_back(to_gray(i));
}

程序代码

#include <cstdio>
using namespace std;
typedef long long ll;
char str1[65],str2[65];
int n;
ll to_bin(ll x){
    ll y = x;
    while(x>>=1){
        y^=x;
    }
    return y;
}
int main(){
    scanf("%d %s %s",&n, str1+1, str2+1);
    ll ans1 = 0;
    for(int i = 1; i<= n; i++){
        ans1 |= (ll)(str1[i] - '0')*(1ll<<(n-i));
    }
    ll ans2 = 0;
    for(int i = 1; i<= n; i++){
        ans2 |= (ll)(str2[i] - '0')*(1ll<<(n-i));
    }
    ll res = to_bin(ans2) - to_bin(ans1) - 1;
    printf("%lld", res); 
    return 0;
}