2019牛客暑期多校训练营（第八场）C CDMA【分形】

题意:

构造一个 n*n 的 只有 1 -1 的方阵
n为 2的1、2、3…10次方
使得任意两行的内积为0

题目链接：

https://ac.nowcoder.com/acm/contest/888/C

题解：

根据样例推出规律
用m的解推出2m的解
m的解 为方阵 A
2m的解 为
A  A
A -A
写法用分形

AC_code:

#include<bits/stdc++.h>
const int maxn = 100005;
int ss[3005][3005];
using namespace std;
int n;
void dfs(int b) {
    if(b == n) {
        return;
    }
    int m = 1<<b;
    for(int i = 0; i < m; i++) {
        for(int j = m; j < 2*m; j++) {
            ss[i][j] = ss[i][j-m];
        }
    }
    for(int i = 0; i < m; i++) {
        for(int j = m; j < 2*m; j++) {
            ss[j][i] = ss[j-m][i];
        }
    }
    for(int i = m; i < 2*m; i++) {
        for(int j = m; j < 2*m; j++) {
            ss[j][i] = -ss[j-m][i-m];
        }
    }
    dfs(b+1);
}
int main() {
    ss[0][0] = 1;
    int num;
    cin>>num;
    int q = num;
    n = 0;
    while(q) {
        q/=2;
        n++;
    }
    dfs(0);
    for(int i = 0; i < num; i++) {
        for(int j = 0; j < num; j++) {
            if(j != 0) printf(" ");
            printf("%d",ss[i][j]);
        }
        puts("");
    }
}