链接
http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1260
今年湘潭的A题
题意不难
大意是把n*(n+1)矩阵去掉某一列
求去掉那一列之后的对应的行列式的值 mod 1e9+7
思路1 :
先做一次高斯消元
得到一个阶梯矩阵 只有最后两列没有被消元
然后每去掉一列 拿出新的矩阵 做一次消元
1 a12 a13 a14
0 1 a23 a24
0 0 1 a34
假设去掉第一列
a12 a13 a14
1 a23 a24
0 1 a34
把第一行添到到最后一行后面
1 a23 a24
0 1 a34
a12 a13 a14
再做一次消元
1 a23 a24
0 1 a34
0 0 s44
然后这一行的ans 就是 s44* 消元的系数
(注意消元时候的除法用逆元 以及去掉最后两列时直接在最初的消元好的矩阵中求解 不再做新的消元)
代码 :
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+;
int pow_mod(int n,int m)
{
int ret=;
while (m){
if (m&)ret=1LL*ret*n%mod;
n=1LL*n*n%mod;
m>>=;
}
return ret;
}
vector<int> a[];
vector<int> st[];
int ans1[];
int ans2[];
inline int up_mod(long long x)
{
return ((x%mod)+mod)%mod;
}
int main()
{
int n;
int i,j,k,l;
while (~scanf("%d",&n)){
n--;
int v;
for (i=;i<=n;i++){
a[i].clear();
a[i].push_back();
ans1[i]=ans2[i]=;
for (j=;j<=n+;j++){
scanf("%d",&v);
a[i].push_back(v);
}
}ans1[n+]=ans2[n+]=;
if (n==){
printf("%d %d\n",a[][],a[][]);
continue ;
}
int det=;
for (i=;i<=n;i++){
for (j=i;j<=n;j++){
if (a[j][i]>)break;
}
if (j==n+)continue;
if (j!=i){
swap(a[i],a[j]);
det=up_mod(-det);
}
det=up_mod(1LL*det*a[i][i]);
int inv=pow_mod(a[i][i],mod-);
for (j=i;j<=n+;j++)a[i][j]=up_mod(1LL*inv*a[i][j]);
for (j=i+;j<=n;j++){
int tmp=a[j][i];
for (k=i;k<=n+;k++){
a[j][k]=up_mod(a[j][k]-1LL*tmp*a[i][k]);
}
}
}
/* for (i=1;i<=n;i++,puts(""))for (j=1;j<=n+1;j++)printf("%12d",a[i][j]);*/
for (i=;i<=n-;i++){
int pre=;
for (j=;j<=n;j++){
if (j==i)st[n]=a[i];
else st[pre++]=a[j];
}
for (k=i+;k<=n;k++){
if (!st[n][k])continue;
int tmp=st[n][k];
for (j=k;j<=n+;j++){
st[n][j]=up_mod(st[n][j]-1LL*st[k-][j]*tmp);
}
}/*puts("");
for (j=1;j<=n;j++,puts("")){
for (k=1;k<=n+1;k++)printf("%10d",st[j][k]);
}*/
int ans=st[n][n+];
pre=;
int mm=det;
if ((n-i)&)mm=up_mod(-det);
printf(i==?"%d":" %d",up_mod(1LL*mm*ans));
}
printf(" %d %d\n",up_mod(1LL*det*a[n][n+]),det);
}
return ;
}
ac 运行时间为218ms
第二种思路是在开头加一行数 然后题目相当于求第一行每个元素对应的代数余子式
等价于求伴随矩阵
下面的代码是qls的 借来一用 思路很清晰
利用逆矩阵求伴随矩阵
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=;
const int Mod=;
int a[MAXN][MAXN],b[MAXN][MAXN];
int get_rand(int x)//[0,x)
{
int t=;
while((<<t)<x)t++;
int res=x;
while(res>=x)
{
res=;
for(int i=;i<t;i++)
res|=(rand()%)<<i;
}
return res;
}
int fp(int a,int k)
{
int res=;
while(k)
{
if(k&)res=1LL*res*a%Mod;
a=1LL*a*a%Mod;
k>>=;
}
return res;
}
void solve(int n)
{
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
b[i][j]=(i==j);
int det=;
for(int i=;i<=n;i++)
{
int t=i;
for(int k=i;k<=n;k++)
if(a[k][i])t=k;
if(t!=i)det*=-;
for(int j=;j<=n;j++)
{
swap(a[i][j],a[t][j]);
swap(b[i][j],b[t][j]);
}
det=1LL*a[i][i]*det%Mod;
int inv=fp(a[i][i],Mod-);
for(int j=;j<=n;j++)
{
a[i][j]=1LL*inv*a[i][j]%Mod;
b[i][j]=1LL*inv*b[i][j]%Mod;
}
for(int k=;k<=n;k++)
{
if(k==i)continue;
int tmp=a[k][i];
for(int j=;j<=n;j++)
{
a[k][j]=(a[k][j]-1LL*a[i][j]*tmp%Mod+Mod)%Mod;
b[k][j]=(b[k][j]-1LL*b[i][j]*tmp%Mod+Mod)%Mod;
}
}
}
det=(det+Mod)%Mod;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
b[i][j]=1LL*det*b[i][j]%Mod;
}
int main()
{
srand(time(NULL));
int n;
while(scanf("%d",&n)!=EOF)
{
for(int j=;j<=n;j++)
a[][j]=;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
scanf("%d",&a[i][j]);
solve(n);
for(int i=;i<=n;i++)
printf("%d%c",(i& ? b[i][] : (Mod-b[i][])%Mod)," \n"[i==n]);
}
return ;
}