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

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

Solution:

```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
for j in range(size):
if csum[j] in vis:
return False
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!")```

```#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;
}
```