牛客多校训练第八场C.CDMA（思维+构造）

HOLLAY 2019-08-11 原文

题意：

输入整数m（ m∈ $2$ ，构造一个由1和-1组成的m×m矩阵，要求对于任意两个不同的行的内积为0。

题解：

Code：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int M=(1<<10)+5;
 4 int ans[M][M];
 5 void solve(int k,int n,int m)
 6 {
 7     if(n==m<<1)
 8         return;
 9     else{
10         for(int i=0;i<n;i++){
11             for(int j=0;j<n;j++){
12                 if(i<n/2||j<n/2)
13                     ans[i][j]=ans[i%k][j%k];
14                 else
15                     ans[i][j]=-ans[i%k][j%k];//右下角部分取相反
16             }
17         }
18     }
19     solve(k<<1,n<<1,m);
20 }
21 int main()
22 {
23     ans[0][0]=1,ans[0][1]=1,ans[1][0]=1,ans[1][1]=-1;
24     int m;
25     cin>>m;
26     solve(2,4,m);
27     for(int i=0;i<m;i++){
28         for(int j=0;j<m;j++){
29             printf("%d ",ans[i][j]);
30         }
31         puts("");
32     }
33     return 0;
34 }

下面贴一份别人的代码，没看懂为什么可以这样解，哪位大佬能来解释解释吗~~

【查了一下，函数_builtin_popcount(n)是计算n的二进制中多少个1】

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1024;
 4 
 5 int a[maxn][maxn];
 6 int n;
 7 
 8 int main()
 9 {
10     scanf("%d",&n);
11     for (int i=0;i<n;i++)
12     for (int j=0;j<n;j++)
13         a[i][j]=(__builtin_popcount(i&j)&1)?-1:1;
14     for (int i=0;i<n;i++)
15     for (int j=0;j<n;j++)
16         printf("%d%c",a[i][j],(j==n-1)?'\n':' ');
17     return 0;
18 }