19年牛客多校8——CDMA（递归）

题意

给你一个$m$($m\in \lbrace 2^k | k=1,2,...,10\rbrace $)，你需要构造一个$m\times m$的矩阵，要求任意两行的内积为$0$，内积也叫点积：对于$a,b$有$a\cdot b=\sum _{i=1}^{n}a_ib_i=a_1b_1+a_2b_2+\cdots +a_nb_n$

思路

构造，当$n=2$的时候，我们构造出

嗯，然后按照下面方法构造，我问大佬们为什么，感觉是对的，他们说“瞎**构造”就好

就是每个这样的小块往其他方向填：

每次递归，有一个$v$，要么是$1$，要么是$-1$，然后往其他地方填

然后这个时候，相当于又是矩阵的开始，这回是$4$个$4\times 4$小矩阵，然后继续往下dfs

然后继续往下传递，继续分成若干个$2\times 2$的矩阵，直到$n=1$的时候填入当前的$v$

如何理解$v$？
这个$v$就是我们之后要填入数字的数，但是会一直变化，比如$-1\times (-1)=1$，这个时候又是$1$了，
正如上图右下角，这整块的$v$ 是-1，但是会随着之后的变化可能会改变，比如最后一个变成了1

如何理解可行性？
我的理解是整体都满足，一开始从小的$2\times 2$的矩阵慢慢变大，同样满足，实际上我们能看出，大的矩阵的$v$进行内积计算还是$0$，所以一直满足

代码

inline void dfs(int i,int j,int n,int v)
{
    if (n==1) {a[i][j]=v;return;}
    dfs(i,j,n/2,v);
    dfs(i+n/2,j,n/2,v);
    dfs(i,j+n/2,n/2,v);
    dfs(i+n/2,j+n/2,n/2,-v);
}

inline void Case_Test()
{
    cin>>n;
    dfs(1,1,n,1);
    rep(i,1,n) rep(j,1,n) cout<<a[i][j]<<" \n"[j==n];
}