QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#44902	#4654. Tree	_whb	WA	1112ms	13680kb	C++11	5.9kb	2022-08-22 11:30:47	2022-08-22 11:30:51

Judging History

你现在查看的是最新测评结果

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2022-08-22 11:30:51]
评测

测评结果：WA
用时：1112ms
内存：13680kb

查看

[2022-08-22 11:30:47]
提交

answer

#include<bits/stdc++.h>

using namespace std ;
#define ll long long
const int MAXN = 505, mod = 998244353 ;
int qsm(int a,int b)
{
    int ans=1 ;
    while(b)
    {
        if(b&1) ans=(ll)ans*a%mod ;
        a=(ll)a*a%mod ; b>>=1 ;
    }
    return ans ;
}
struct Matrix
{
    int m[MAXN][MAXN] ;
    Matrix() { memset(m,0,sizeof(m)) ; }
} ;
namespace Mat
{
    int A[MAXN][MAXN],B[MAXN][MAXN<<1] ;
    Matrix mat_ret,mat_lin ;
    #define up(i,a,b) for(int i=(a);i<=(b);++i)
    #define rep(i,a,b) for(int i=(a);i>=(b);--i)
    #define VI vector<int>
    void ad(int &x,int y) { x+=y ; if(x>=mod) x-=mod ; }
    void dl(int &x,int y) { x-=y ; if(x<0) x+=mod ; }
    int det(const Matrix &a,int n)//矩阵求行列式
    {
        up(i,1,n)up(j,1,n) A[i][j]=a.m[i][j] ;
        int ret=1 ;
        up(i,1,n)
        {
            int u=i ; up(j,i+1,n) if(A[j][i]) { u=j ; break ; }
            if(u!=i) { up(j,i,n) swap(A[u][j],A[i][j]) ; ret=(ll)ret*(mod-1)%mod ; }
            if(!A[i][i]) return 0 ; int Iv=qsm(A[i][i],mod-2) ;
            up(j,i+1,n)
            {
                int tmp=(ll)A[j][i]*Iv%mod ;
                up(k,i,n) dl(A[j][k],(ll)tmp*A[i][k]%mod) ;
            }
            ret=(ll)ret*A[i][i]%mod ;
        }
        return ret ;
    }
    Matrix mat_inv(const Matrix &a,int n)//矩阵求逆
    {
        memset(B,0,sizeof(B)) ; int l=n<<1 ;
        up(i,1,n)up(j,1,n) B[i][j]=a.m[i][j] ;
        up(i,1,n) B[i][i+n]=1 ;
        up(i,1,n)
        {
            int u=i ; up(j,i+1,n) if(B[j][i]) { u=j ; break ; }
            up(j,1,l) swap(B[i][j],B[u][j]) ;
            int Iv=qsm(B[i][i],mod-2) ;
            up(j,1,l)
            {
                if(i==j) continue ;
                int tmp=(ll)B[j][i]*Iv%mod ;
                up(k,i,n) dl(B[j][k],(ll)tmp*B[i][k]%mod) ;
                up(k,n+1,l) dl(B[j][k],(ll)tmp*B[i][k]%mod) ;
            }
            up(j,i,n) B[i][j]=(ll)B[i][j]*Iv%mod ;
            up(j,n+1,l) B[i][j]=(ll)B[i][j]*Iv%mod ; 
        }
        memset(mat_ret.m,0,sizeof(mat_ret.m)) ;
        up(i,1,n)up(j,1,n) mat_ret.m[i][j]=B[i][j+n] ;
        return mat_ret ;
    }
    int calc_r(const Matrix &a,int n)//矩阵求秩
    {
        up(i,1,n)up(j,1,n) A[i][j]=a.m[i][j] ;
        int ret=0 ;
        up(i,1,n)
        {
            if(!A[i][i])
            {
                int u=-1  ;
                up(j,i+1,n) if(A[j][i]) { u=j ; break ; }
                if(u==-1) continue ;
                up(j,i,n) swap(A[i][j],A[u][j]) ;
            }
            ret++ ; int Iv=qsm(A[i][i],mod-2) ;
            up(j,i+1,n)
            {
                int tmp=(ll)A[j][i]*Iv%mod ;
                up(k,i,n) dl(A[j][k],(ll)tmp*A[i][k]%mod) ;
            }
        }
        return ret ;
    }
    Matrix get_adjoint_matrix_full(const Matrix &a,int n)//求满秩矩阵伴随矩阵
    {
        Matrix Iv=mat_inv(a,n) ; int Z=det(a,n) ;
        up(i,1,n)up(j,1,n) mat_ret.m[j][i]=(ll)Iv.m[i][j]*Z%mod ;
        return mat_ret ;
    }
    int us[MAXN][MAXN],Inv[MAXN] ;
    VI insert(VI Z,int n,int id)
    {
        VI bel(n+1,0) ; bel[id]=1 ; bel[0]=-1 ;
        rep(i,n,1) if(Z[i])
        {
            if(!A[i][i])
            {
                rep(j,i,1) A[i][j]=Z[j] ;
                Inv[i]=qsm(A[i][i],mod-2) ;
                up(j,1,n) us[i][j]=bel[j] ;
                return bel ;
            }
            int tmp=(ll)Inv[i]*Z[i]%mod ;
            rep(j,i,1) dl(Z[j],(ll)tmp*A[i][j]%mod) ;
            up(j,1,n) dl(bel[j],(ll)tmp*us[i][j]%mod) ;
        }
        bel[0]=0 ; return bel ;
    }
    VI get_G(const Matrix &a,int n,int op) //求线性相关系数
    {
        VI ret ;
        up(i,1,n)up(j,1,n) A[i][j]=a.m[i][j] ;
        if(op) up(i,1,n)up(j,1,n) B[j][i]=A[i][j] ;
        else up(i,1,n)up(j,1,n) B[i][j]=A[i][j] ;
        memset(A,0,sizeof(A)) ; memset(us,0,sizeof(us)) ;
        up(i,1,n)
        {
            VI Z(n+1,0) ;
            up(j,1,n) Z[j]=B[j][i] ;
            ret=insert(Z,n,i) ;
            if(ret[0]!=-1) return ret ;
        }
    }
    Matrix get_adjoint_matrix_one(const Matrix &a,int n)//求秩为n-1的矩阵伴随矩阵
    {
        VI Q = get_G(a,n,0) ; // 列向量组系数
        VI P = get_G(a,n,1) ; // 行向量组系数
        int c=-1,r=-1 ;
        up(i,1,n) if(Q[i]) { c=i ; break ; }
        up(i,1,n) if(P[i]) { r=i ; break ; }
        up(i,1,n) if(i!=r) up(j,1,n) if(j!=c)
            mat_lin.m[i-(i>r)][j-(j>c)]=a.m[i][j] ;
        int Ivq=qsm(Q[c],mod-2),Ivp=qsm(P[r],mod-2) ;
        int Iv=(ll)Ivp*Ivq%mod ;
        mat_ret.m[r][c]=det(mat_lin,n-1) ;
        if((r+c)&1) mat_ret.m[r][c]=mod-mat_ret.m[r][c] ;
        up(i,1,n)up(j,1,n)
        {
            int val=(ll)P[i]*Q[j]%mod*Iv%mod*mat_ret.m[r][c]%mod ;
            mat_ret.m[i][j]=val ;
        }
        return mat_ret ;
    } 
    // A * A* = |A| * I
    Matrix get_adjoint_matrix(const Matrix &a,int n)//求矩阵的伴随矩阵
    {
        int Z=calc_r(a,n) ;
        if(Z==n) return get_adjoint_matrix_full(a,n) ;
        else if(Z==n-1) return get_adjoint_matrix_one(a,n) ;
        else 
        {
            memset(mat_ret.m,0,sizeof(mat_ret.m)) ;
            return mat_ret ;
        }
    }
}
int n,m ;
int w[MAXN][MAXN],ind[MAXN] ;
Matrix a,b ;
void solve()
{
    scanf("%d%d",&n,&m) ;
    for(int i=1;i<=n;++i)
    {   
        ind[i]=0 ;
        for(int j=1;j<=n;j++)
            a.m[i][j]=b.m[i][j]=w[i][j]=0 ;
    }
    for(int i=1,x,y;i<=m;++i)
    {
        scanf("%d%d",&x,&y) ;
        w[x][y]++ ;
        ind[y]++ ;
    }
    for(int i=1;i<=n;++i)
    {
        a.m[i][i]=ind[i] ;
        for(int j=1;j<=n;j++)
            a.m[i][j]=(a.m[i][j]+mod-w[i][j])%mod ;
    }
    b=Mat::get_adjoint_matrix(a,n) ;
    for(int i=1;i<=n;++i)
        printf("%d%c",b.m[i][i]%mod,(i==n)?'\n':' ') ;
}
int main()
{
    int T ; scanf("%d",&T) ;
    while(T--) solve() ;
    return 0 ;
}

源文件, 语言: C++11

详细

Test #1:

score: 0

Wrong Answer

time: 1112ms

memory: 13680kb

input:

output:

2 3 1 4 2 6 2
1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0
275294437 275294437 275294437 275294437 275294437 275294437 275294437 275294...

result:

wrong answer 7th lines differ - expected: '850518977 850518977 850518977 ...7 850518977 850518977 850518977', found: '275294437 275294437 275294437 ...7 275294437 275294437 275294437'