牛客多校第八场 C CDMA 线性代数：沃尔什矩阵

题意：

构造出一个由1和-1组成的$2^k*2^k$的矩阵，使得矩阵任意两列内积为0

题解：

数学知识，沃尔什矩阵。沃尔什矩阵的特性被CDMA（码分多址）采用，使得编码成为无线信号的频段和振幅之外的第三维，提高了无线信道利用率。

构造沃尔什矩阵只需倍增构造，以第i个矩阵的第k行重复两遍，作为第i+1个矩阵的第2k行，取正一遍，取反一遍，作为第i+1个矩阵的第2k+1行。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<stack>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXN 100000+50
#define MAXM 30000
#define ll long long
#define per(i,n,m) for(int i=n;i>=m;--i)
#define rep(i,n,m) for(int i=n;i<=m;++i)
#define mod 1000000000 + 7
#define mian main
#define mem(a, b) memset(a, b, sizeof a)
#ifndef ONLINE_JUDGE
#define dbg(x) cout << #x << "=" << x << endl;
#else
#define dbg(x)
#endif
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = 10 * x + ch - '0';
        ch = getchar();
    }
    return x * f;
}
inline ll readll()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = 10 * x + ch - '0';
        ch = getchar();
    }
    return x * f;
}
int a[15][2000][2000];
void init()
{
    a[1][1][1] = 1;
    for (int i = 2; i <= 11; ++i)
    {
        int t = pow(2, i-1);
        for (int j = 1; j <= t;j++)
        {
            for (int k = 1; k <= t / 2; ++k)
            {
                a[i][j][k] = a[i - 1][(j + 1) / 2][k];
            }
            if (j & 1)
            {
                for (int k = t/2+1; k <= t; ++k)
                {
                    a[i][j][k] = a[i - 1][(j + 1) / 2][k-t/2];
                }
            }
            else
            {
                for (int k = t / 2 + 1; k <= t; ++k)
                {
                    a[i][j][k] =- a[i - 1][(j + 1) / 2][k-t/2];
                }
            }
        }
    }
}
int main()
{
    int _ = 1;
    init();
    while (_--)
    {
        int n = read();
        int num = 0;
        int t = n;
        while (t)
        {
            t >>= 1;
            num++;
        }
        for(int i=1;i<=n;++i)
            for (int j = 1; j <= n; ++j)
            {
                printf("%d%c", a[num][i][j], " 
"[j == n]);
            }
    }
}