NOIP 提高 2011 第一轮 第 26 题：枚举二进制向量求汉明距离总和

题目

```
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
const int SIZE=10000;
const int LENGTH=10;
int n,m,a[SIZE][LENGTH];
int h(int u,int v)
{
    int ans,i;
    ans=0;
    for(i=1;i<=n;i++)
       if( a[u][i]!=a[v][i])
           ans++;
    return ans;
}
int main()
{
    int sum,i,j;
    cin>>n;
    memset(a,0,sizeof(a));
    m=1;
    while(1)
    {
        i=1;
        while( (i<=n) && (a[m][i]==1) )
            i++;
        if(i>n)
           break;
        m++;
        a[m][i]=1;
        for(j=i+1;j<=n;j++)
           a[m][j]=a[m-1][j];
    }
    sum=0;
    for(i=1;i<=m;i++)
       for(j=1;j<=m;j++)
          sum+=h(i,j);
    cout<<sum<<endl;
    return 0;
}
```
输入：7  
输出：_________

请写出程序的输出结果。

答案

57344

题解

考点定位

本题考「汉明距离求和」,对应大纲 2.1.2 位运算（难度【4】）。

解题过程

枚举所有 7 位二进制向量（128 个），求所有向量对的汉明距离之和。对称计数：每一位上，64 个向量该位为 1、64 个为 0，异或不同的向量对 = 64×64 = 4096/位。7 位：

$$7\times64\times64=28672$$

答案：28672。

易错提醒

① 「对称计数」：按位统计而非枚举 C(128,2) 对；② 每位上 1 的个数 = 2⁶=64。