題目鏈接

題目描述：

給出一個N*N的方陣A。構造方陣B,C:
使得A = B + C.其中 B為對稱矩陣，C為反對稱矩陣。
對于方陣S中的任意元素,若(S)ij = (S)ji,則稱S為對稱矩陣
對于方陣T中的任意元素,若(T)ij = -(T)ji,則稱T為反對稱矩陣
注意，所有運算在模M意義下

輸入描述：

輸入包含多組數(shù)據(jù)，處理到文件結束
每組數(shù)據(jù)，第一行包含兩個正整數(shù)N,M(1 <= N <= 1000, 1 <= M <= 1000,000,001)分別表示方陣大小與模數(shù)，其中M必定為奇數(shù)。
接下來的N行，每行有N個非負整數(shù)，表示方陣A(0<=Aij<=1000,000,000)。

輸出描述：

對于每組數(shù)據(jù)，將反對稱矩陣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 結果還是負數(shù) //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-对称与反对称（扩展欧几里得求逆元）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。