“景驰科技杯”2018年华南理工大学程序设计竞赛 H 对称与反对称

Description:

给出一个N*N的方阵A。构造方阵B,C:
使得A = B + C.其中 B为对称矩阵，C为反对称矩阵。
对于方阵S中的任意元素,若(S)ij = (S)ji,则称S为对称矩阵
对于方阵T中的任意元素,若(T)ij = -(T)ji,则称T为反对称矩阵
注意，所有运算在模M意义下

Input:

输入包含多组数据，处理到文件结束
每组数据，第一行包含两个正整数N,M(1 <= N <= 1000, 1 <= M <= 1000,000,001)分别表示方阵大小与模数，其中M必定为奇数。
接下来的N行，每行有N个非负整数，表示方阵A(0<=Aij<=1000,000,000)。

Output:

对于每组数据，将反对称矩阵 $C$C在 $N$N行中输出；
若不存在解，则输出"Impossible"；
若存在多解，则输出任意解。

Sample Input:

2 19260817
0 1
1 0

Sample Output:

0 0
0 0

题目链接

矩阵主对角线不用考虑，先设A为：
$\left[\begin{array}{cc}0& C1\\ C2& 0\end{array}\right]$[0C2​C10​]
设B为:
$\left[\begin{array}{cc}0& x\\ x& 0\end{array}\right]$[0x​x0​]
设C为:
$\left[\begin{array}{cc}0& y\\ -y& 0\end{array}\right]$[0−y​y0​]
则可得公式:
$(x+y)\%m=C1(x-y)\%m=C2$(x+y)%m=C1(x−y)%m=C2
化简可得
$y=\left(\right(C1-C2)÷2)\%m$y=((C1−C2)÷2)%m
这里就得到了反对称矩阵C和输入矩阵A的关系式。
但是这个求解方程式中存在除法和取模的计算，这就需要用逆元来计算了。一篇解释逆元挺清楚的博文——>逆元(其实我理解的逆元就是在模关系下的倒数)。
求逆元又需要用到拓展欧几里得算法:

扩展欧几里德算法是用来在已知a, b求解一组x，y，使它们满足贝祖等式： ax+by = gcd(a, b) =d
——百度百科

拓展欧几里得算法模板:

// 返回值为d(=gcd(a, b)),和ax+by=d中的x,y
long long extendgcd(long long a, long long b, long long &x, long long &y) {
    if (a == 0 && b == 0) {
        return -1;
    }
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extendgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

求逆元模板:

// 返回值为a关于mod的逆元
long long inverse(long long a, long long mod) {
    long long x, y;
    long long d = extendgcd(a, mod, x, y);
    if (d == 1) {
        return (x % mod + mod) % mod;
    }
    else {
        return -1;
    }
}

输出中每行行尾无多余空格。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 1e3+5;
const double eps = 1e-5;
const double e = 2.718281828459;

int n;
ll m;
ll A[maxn][maxn];
ll C[maxn][maxn];

ll extendgcd(ll a, ll b, ll &x, ll &y) {
    if (a == 0 && b == 0) {
        return -1;
    }
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll d = extendgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

ll inverse(ll a, ll mod) {
    ll x, y;
    ll d = extendgcd(a, mod, x, y);
    if (d == 1) {
        return (x % mod + mod) % mod;
    }
    else {
        return -1;
    }
}

void antisymmetric_matrix() {
    ll inv = inverse(2, m);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i < j) {
                C[i][j] = (A[i][j] - A[j][i]) * inv % m;
                C[j][i] = -C[i][j];
                while (C[i][j] < 0) {
                    C[i][j] += m;
                }
                while (C[j][i] < 0) {
                    C[j][i] += m;
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    while (cin >> n >> m) {
        mem(A, 0);
        mem(C, 0);
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                cin >> A[i][j];
            }
        }
        antisymmetric_matrix();
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                cout << C[i][j];
                if (j != n) {
                    cout << " ";
                }
            }
            cout << endl;
        }
    }
    return 0;
}