【FZU-1911】Construct a Matrix【构造问题】

【FZU-1911】Construct a Matrix【构造问题】

问题链接:https://vjudge.net/problem/FZU-1911

Solution:

矩阵的大小使用矩阵快速幂来求就好,方法是,给以往的斐波那契变换矩阵加上一行,用来记录和值。接着就是一个构造问题了,我们写一个程序来单独跑dfs【为了编码方便,我就使用python3来写了,毕竟代码会精简一些】,需要的功能是,给出一个边长,遍历所有可能的矩阵,都进行输出:

import numpy as np
# try to build a valid matrix by using dfs
def dfs(size, crt, ans):
    if crt == size * size:
        vis = set([])
        csum = np.zeros(size, int)
        for i in range(size):
            rsum = 0
            for j in range(size):
                rsum = rsum + ans[i * size + j]
                csum[j] = csum[j] + ans[i * size + j]
            if rsum in vis:
                return False
            vis.add(int(rsum))
        for j in range(size):
            if csum[j] in vis:
                return False
            vis.add(int(csum[j]))
        print("Find one solution!")
        print(ans.reshape(size, size))
        return True
    flag = False
    for i in range(-1, 2):
        ans[crt] = i
        # print("Current : ", ans)
        flag = dfs(size, crt + 1, ans) or flag
    return flag

size = int(input("The size of matrix to construct:"))
ans = np.zeros(size * size, int);
if not dfs(size, 0, ans):
    print("Unfortunately, there are no valid solutions!")
else:
    print("All solution have been showed!")

首先我们可以发现的是,如果边长是奇数或者0,是不存在符合要求的矩阵的,接着就是找偶数的情况。按照上面的程序,输出会很多,我们通过一些猜想来做些简单的修改,来添加一些要求,让它不要把任何满足要求的排列的矩阵都输出。最后我们可以发现一种构造方法:对于n阶矩阵,如果n是一个非零偶数,那么总存在至少一种排列方法,使得其满足:只包含0,-1,1三种元素,且各行各列的和值不相同,其中一种有效的构造方法是,将矩阵按照一条对角线分隔开,对角线上方放置1或-1,下方放置与上方的数相反的数,分割用的对角线上交替放置0,1或0,-1。

#include <iostream>
#include <cstdio>
#include <set>

using namespace std;

typedef long long LL;
const int LIM = 200 + 10;
int size;
LL n, m;
int ans[LIM * LIM];
int csum[LIM], rsum;

struct Matrix {
    LL v[3][3];
    Matrix operator * (const Matrix &m) const {
        Matrix ret = {0};
        for (int i = 0; i < 3; i++)
            for (int k = 0; k < 3; k++)
                if (v[i][k])
                    for (int j = 0; j < 3; j++)
                        ret.v[i][j] = (ret.v[i][j] + v[i][k] * m.v[k][j]) % ::m;
        return ret;
    }
};

int fibonacci(LL n, Matrix base) {
    Matrix ret = {0};
    ret.v[0][0] = ret.v[1][0] = 1;
    while (n) {
        if (n & 1) ret = base * ret;
        n >>= 1;
        if (n) base = base * base;
    }
    return ret.v[2][0];
}

int main(void) {
    ios::sync_with_stdio(false);
    // cin.tie(NULL);
    int t;
    cin >> t;
    Matrix base = {1, 1, 0, 1, 0, 0, 0, 1, 1};
    for (int k = 1; k <= t; k++) {
        cin >> n >> m;
        size = fibonacci(n, base);
        if (!size || size & 1) {
            cout << "Case " << k << ": No" << "\n";
        } else {
            cout << "Case " << k << ": Yes" << "\n";
            for (int i = 0; i < size; i++) {
                for (int j = 0; j < size; j++) {
                    if (j) cout << ' ';
                    if (i == j) cout << (i & 1 ? 0 : -1);
                    else if (j < i) cout << 1;
                    else cout << -1;
                }
                cout << '\n';
            }
        }
    }
    return 0;
}