百度笔试 第三题 加减交替一个可能的思路

数组 a[n]，每次+-交替
测试用例
数组 {1, 2, 3, 4}
1+2, 2-3, 3+4:  {3, -1, 7}
3-(-1), -1+7: {4, 6}
4-6: {2}
我们抽象出一个数组{a,b,c,d}
起始我们的矩阵是
1000
0100
0010
0001
然后经过一轮的加减加
1 1 0 0
0 1 -1 0
0 0 1 1
第三轮
1 0 1 0
0 1 0 1
最后一轮
1 -1 1 -1
规律不太够，也不知道这样暴力迭代矩阵能不能过
但有一个优化思路
我们再对5 *5的矩阵做规律观察
10000
01000
00100
00010
00001
->
1 1 0 0 0
0 1 -1 0 0
0 0 1 1 0
0 0 0 1 -1
->
1 2 -1 0 0
0 1 2 -1 0
0 0 1 2 -1
->
1 3 1 -1 0
0 1 3 1 -1
->
1 0 2 0 1
我们发现从第三轮开始，每一轮的矩阵有很强的重复性，所以可能可以在这上面优化
当然如果迭代完能ac那可以不考虑这层优化
以下矩阵计算代码
int n;
cin>>n;
    vector> matrix(n,vector(n,0));
       
    //初始化成一个单位矩阵
    for(int i = 0;i        matrix[i][i] = 1;
    //加减交替滚动计算矩阵
    //第一行加第二行，第二行减第三行
    bool flag = true;
    while(matrix.size() != 1){
        for(int i = 0;i < matrix.size() - 1;i++){
            for(int j = 0;j                if(flag) {
                    matrix[i][j] += matrix[i + 1][j];
                }
                else{
                    matrix[i][j] -= matrix[i+1][j];
                } 
            }
            flag == true? flag = false:flag = true;
        }
        matrix.pop_back();
    }
    for(int i = 0;i        cout<    }