2018华南理工大学程序设计竞赛 H-对称与反对称

2018/04/11 22:58
阅读数 15

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<=A
ij
<=1000,000,000)。

输出描述:

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

输入

2 19260817
0 1
1 0

输出

0 0
0 0

思路:任意的矩阵A,必定存在对称矩阵(A+A^T)/2和反对称矩阵(A-A^T)/2;
坑点在于运算是在模运算意义下的,并且(A-A^T)/2的每一个元素都是分数,对分数求模运算,除2可以当作是乘2的逆元2^-1,即(A-A^T)/2%MOD等价于(A-A^T)*(2^-1)%MOD。
AC代码:
#define _CRT_SECURE_NO_DEPRECATE
#include <iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<bitset>
using namespace std;
#define N_MAX 21
#define M_MAX 21
#define MOD 1000000009
#define INF 0x3f3f3f3f
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

int n;ll m;ll mod;
mat sum(mat &A) {
    mat C(A.size(), vec(A.size()));
    for (int i = 0; i < n;i++) {
        for (int j = 0; j < n;j++) {
            C[i][j] = ((A[i][j] -A[j][i])*m%mod+mod)%mod;
      }
    }
    return C;
}
int e_gcd(int a,int b,int &x,int &y){
   if(b==0){
     x=1;y=0;return a;
   }
   int ans=e_gcd(b,a%b,x,y);
   int temp=x;
   x=y;
   y=temp-a/b*y;
   return ans;
}
int mod_inverse(int a,int m){
  int x,y;
  e_gcd(a,m,x,y);
  return (m+x%m)%m;
}

int main() {
    while(scanf("%d%lld",&n,&mod)!=EOF) {
        m=mod_inverse(2,mod);
        mat A(n, vec(n));
        for (int i = 0; i < n;i++) {
            for (int j = 0; j < n; j++) {
                scanf("%lld",&A[i][j]);
            }
        }
        mat C = sum(A);
        for (int i = 0; i < C.size();i++) {
            for (int j = 0; j < C.size();j++) {
                printf("%lld%c",C[i][j],j+1==C.size()?'\n':' ');
            }
        }
    }
    return 0;
}

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部