“景驰科技杯”2018年华南理工大学程序设计竞赛 H-对称与反对称（扩展欧几里得求逆元）

题目链接

题目描述：

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

输入描述：

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

输出描述：

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

输入：

2 19260817
0 1
1 0

输出：

0 0
0 0

解题思路：

如果一个矩阵可以表示为对称矩阵和反对称矩阵的和，那么这个反对称矩阵就是原矩阵对称位置的差的一半。不好解释自行理解…
因为所有运算在模M意义下，所以 (a - b) / 2 % m,就可以转化为 (a - b) * inverse(2, m)

关于求逆元有个板子

看这里

AC代码：

#include<bits/stdc++.h> #define ll long long #define N 1005 int inf = 0x3f3f3f3f; using namespace std; ll extgcd(ll a, ll b, ll &x, ll &y){ //扩展欧几里得；计算a%b，a关于b的逆元X,b关于a的逆元Y ll d = a;if(b == 0){x = 1;y = 0;}else{d = extgcd(b, a % b, y, x);y -= a / b * x;}return d; //返回a%b } ll inv(ll a, ll mod){ //求a对mod的逆元 ll x, y;int d = extgcd(a, mod, x, y);if(d != 1)return -1;elsereturn (x + mod) % mod;} ll a[N][N], b[N][N]; int main (){ ios::sync_with_stdio(false); cin.tie(0);ll n, m;while(cin >> n >> m){memset(a, 0, sizeof(a));memset(b, 0, sizeof(b));for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){cin >> a[i][j];}}ll invm = inv(2, m);if(invm == -1)cout << "Impossible\n";else{for(int i = 1; i <= n; i++){for(int j = i + 1; j <= n; j++){ll t = (a[i][j] - a[j][i]) * invm % m;//错误写法：当t < 0 && -t > m 结果还是负数 //b[i][j] = t + m % m;//b[j][i] = -t + m % m;//写法一： // b[i][j] = t; // b[j][i] = -t; // while(b[i][j] < 0) // b[i][j] += m; // while(b[j][i] < 0) // b[j][i] += m;//写法二：b[i][j] = (t % m + m) % m;b[j][i] = (-t % m + m) % m; }}for(int i = 1; i <= n; i ++){for(int j = 1; j <=n; j ++){cout << b[i][j];if(j != n)cout << " ";}cout << endl;} } } return 0; }

总结

以上是生活随笔为你收集整理的“景驰科技杯”2018年华南理工大学程序设计竞赛 H-对称与反对称（扩展欧几里得求逆元）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。