bzoj 2107: Spoj2832 Find The Determinant III 辗转相除法
2024-09-19 07:33:50
2107: Spoj2832 Find The Determinant III
Time Limit: 1 Sec Memory Limit: 259 MB
Submit: 154 Solved: 46
[Submit][Status][Discuss]
Description
Problem code: DETER3
Given a NxN matrix A, find the Determinant of A % P.
给出一个尺寸为N×N的整数方阵A(N≤200),要求求出|A|%P的值(即A的行列式的值除以P的余数)。方阵中的数与P均为32位有符号类型可容纳的整数
Input
The first line of every test case contains two integers , representing N
(0 < N < 201) and P (0 < P < 1,000,000,001). The following N
lines each contain N integers, the j-th number in i-th line represents
A[i][j] (- 1,000,000,001 < A[i][j] < 1,000,000,001).
(0 < N < 201) and P (0 < P < 1,000,000,001). The following N
lines each contain N integers, the j-th number in i-th line represents
A[i][j] (- 1,000,000,001 < A[i][j] < 1,000,000,001).
Output
For each test case, print a single line contains the answer.
Sample Input
3 4
-840419217 -895520213 -303215897
537496093 181887787 -957451145
-305184545 584351123 -257712188
-840419217 -895520213 -303215897
537496093 181887787 -957451145
-305184545 584351123 -257712188
Sample Output
2
其实一说算法名称大概都会做了吧。高斯消元的除法本质上等效与辗转相处法,而辗转相处不存在精度误差。我们为了把两行之一消掉,通过辗转相除大行减小行变成类似子问题。
最开始尝试用java的BigDecimal,结果发现精度和时间是不可同时满足的。
矩阵行列式求法可几何理解,向量(基底)可以互相加减,而不影响体积,然而基底互换,有向体积取反。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 210
typedef long long qword;
qword mat[MAXN][MAXN]; int main()
{
//freopen("input.txt","r",stdin);
int n,m,x,y,z;
int mod;
while (~scanf("%d%d",&n,&mod))
{
for (int i=;i<=n;i++)
{
for (int j=;j<=n;j++)
{
scanf("%lld",&mat[i][j]);
mat[i][j]%=mod;
}
}
int rev=;
for (int i=;i<=n;i++)
{
x=-;
for (int j=i;j<=n;j++)
{
if (mat[j][i])
{
x=j;
break;
}
}
if (x==-)break;
if (x!=i)
{
for (int j=;j<=n;j++)
swap(mat[x][j],mat[i][j]);
rev=-rev;
}
if (!mat[i][i])break;
for (int j=i+;j<=n;j++)
{
while (mat[i][i])
{
qword t=mat[j][i]/mat[i][i];
for (int k=;k<=n;k++)
mat[j][k]=(mat[j][k]-mat[i][k]*t)%mod;
for (int k=;k<=n;k++)
swap(mat[j][k],mat[i][k]);
rev=-rev;
}
for (int k=;k<=n;k++)
swap(mat[j][k],mat[i][k]);
rev=-rev;
}
}
qword ans=;
for (int i=;i<=n;i++)
ans=ans*mat[i][i]%mod;
ans=(ans*rev+mod)%mod;
printf("%lld\n",ans);
}
}
最新文章
- React学习笔记-4-什么是生命周期
- Poj2676
- Understanding RabbitMQ Exchange &; Queue
- java List 和Map的使用
- 151102SQL语句
- 【你吐吧c#每日学习】11.10 C# Data Type conversion
- ARM字节对齐问题详解
- NodeJS异常处理uncaughtException篇
- [Locked] Shortest Word Distance I &; II &; III
- tab一些 添加 删除 搜索
- JAVA中获取当前运行的类名,方法名,行数
- 如何通过 WebP 兼容减少图片资源大小
- Jenkins 集群搭建
- hdu2838树状数组解逆序
- for循环中的 break和continue的区别
- C#:struct的陷阱:无法修改“xxx”的返回值,因为它不是变量
- 612.1.004 ALGS4 | Elementary Sorts - 基础排序算法
- 认识hasLayout——IE浏览器css bug的一大罪恶根源 (转)
- 使用阿里云Docker镜像加速
- Linux_LVM Couldn&#39;t find device with uuid
热门文章
- Java并发——使用Condition线程间通信
- GridView中使用如下button OnClientClick代码会出现解析错误
- 20160328 javaweb Cookie 小练习
- com.android.builder.packaging.DuplicateFile
- PHPSession-完全PHP5之session篇
- Android开发环境搭建(2015年8月更新)
- AudioStreamer使用之快速点击下/上一首按钮,音频会重复的问题解决。
- O-C-11-利用类方法做一个简单的计算器
- html-----016---HTTP 状态消息
- phaser源码解析(三) Phaser.Utils类下isPlainObject方法