QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#100635#59. Determinant of A+BzCharlieVinnieJudging//C++174.1kb2023-04-27 14:39:022024-03-04 04:40:46

Judging History

你现在查看的是测评时间为 2024-03-04 04:40:46 的历史记录

  • [2024-05-05 11:54:08]
  • hack成功,自动添加数据
  • (/hack/617)
  • [2024-05-05 11:38:15]
  • hack成功,自动添加数据
  • (/hack/616)
  • [2024-03-04 04:44:33]
  • 管理员手动重测本题所有提交记录
  • 测评结果:97
  • 用时:658ms
  • 内存:9204kb
  • [2024-03-04 04:40:46]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:Judging
  • 用时:790ms
  • 内存:8744kb
  • [2024-03-04 04:35:40]
  • hack成功,自动添加数据
  • (/hack/552)
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-27 14:39:06]
  • 评测
  • 测评结果:100
  • 用时:790ms
  • 内存:8744kb
  • [2023-04-27 14:39:02]
  • 提交

answer

#include "bits/stdc++.h"
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
#define assume(expr) ((!!(expr))||(exit((fprintf(stderr,"Assumption Failed: %s on Line %d\n",#expr,__LINE__),-1)),false))
using namespace std;
template<int mod>
class CharPoly{
protected:
    int qpow(int x,int y){int res=1;while(y){if(y&1)res=1ll*res*x%mod;x=1ll*x*x%mod;y>>=1;}return res;}
public:
    vector<int> operator() (vector<vector<int>> A){ // det(A+Ix), instead of det(Ix-A)
        int n=A.size();
        For(i,1,n-1){
            if(!A[i][i-1]){
                For(j,i+1,n-1) if(A[j][i-1]){
                    swap(A[i],A[j]);
                    For(k,0,n-1) swap(A[k][i],A[k][j]);
                    break;
                }
            }
            if(!A[i][i-1]) continue;
            For(j,i+1,n-1) if(A[j][i-1]){
                int r=(mod-1ll*A[j][i-1]*qpow(A[i][i-1],mod-2)%mod)%mod;
                For(k,0,n-1) A[j][k]=(A[j][k]+1ll*A[i][k]*r)%mod;
                For(k,0,n-1) A[k][i]=(A[k][i]-1ll*A[k][j]*r%mod+mod)%mod;
            }
        }
        vector<vector<int>> F(n+1); F[0].push_back(1);
        For(i,0,n-1){
            F[i+1].resize(i+2);
            For(j,0,i){
                int tt=1ll*A[j][i]*((i-j)&1?mod-1:1)%mod; For(k,j,i-1) tt=1ll*tt*A[k+1][k]%mod;
                For(k,0,j) F[i+1][k]=(F[i+1][k]+1ll*F[j][k]*tt)%mod;
            }
            For(k,0,i) F[i+1][k+1]=(F[i+1][k+1]+F[i][k])%mod;
        }
        return F[n];
    }
};
template<int mod>
class Det_A_Bz : public CharPoly<mod>{
    using CharPoly<mod>::qpow;
public:
    vector<int> operator() (vector<vector<int>> A,vector<vector<int>> B){ // det(A+Bz)
        int n=A.size(),X=0,sw=0; assert(B.size()==1u*n);
        For(i,0,n-1){
            if(!B[i][i]){
                For(j,i+1,n-1) if(B[j][i]) { swap(B[i],B[j]); swap(A[i],A[j]); sw^=1; break; }
            }
            if(!B[i][i]){
                For(j,i+1,n-1) if(B[i][j]){
                    For(k,0,n-1) swap(B[k][i],B[k][j]),swap(A[k][i],A[k][j]);
                    sw^=1; break;
                }
            }
            if(!B[i][i]){
                B[i]=A[i]; A[i].assign(n,0); X++;
                if(X>n) return vector<int>(n+1);
                For(j,0,i-1) if(B[i][j]){
                    int r=-1ll*B[i][j]*qpow(B[j][j],mod-2)%mod;
                    For(k,j,n-1) B[i][k]=(B[i][k]+1ll*B[j][k]*r)%mod;
                    For(k,0,n-1) A[i][k]=(A[i][k]+1ll*A[j][k]*r)%mod;
                }
            }
            if(!B[i][i]){
                return vector<int>(n+1);
            }
            int iv=qpow(B[i][i],mod-2);
            For(j,0,n-1) if(j!=i&&B[j][i]){
                int r=-1ll*B[j][i]*iv%mod;
                For(k,i,n-1) B[j][k]=(B[j][k]+1ll*B[i][k]*r)%mod;
                For(k,0,n-1) A[j][k]=(A[j][k]+1ll*A[i][k]*r)%mod;
            }
        }
        cerr<<"Time2: "<<clock()<<'\n';
        int tt=sw?mod-1:1;
        For(i,0,n-1) if(B[i][i]!=1){
            B[i][i]=(B[i][i]+mod)%mod;
            int iv=qpow(B[i][i],mod-2);
            For(j,0,n-1) A[i][j]=(1ll*A[i][j]*iv%mod+mod)%mod;
            tt=1ll*tt*B[i][i]%mod;
        }
        cerr<<"Time1: "<<clock()<<'\n';
        vector<int> res=CharPoly<mod>::operator()(A);
        For(i,0,n) res[i]=1ll*res[i]*tt%mod;
        For(i,0,n-X) res[i]=res[i+X];
        For(i,n-X+1,n) res[i]=0;
        return res;
    }
};
const int N=505; typedef long long ll;
mt19937 rng(190345);
signed main(){
    int n=500; cin>>n; vector<vector<int>> A(n),B(n);
    For(i,0,n-1){
        A[i].resize(n); for(int& x:A[i]) cin>>x;
    }
    For(i,0,n-1){
        B[i].resize(n); for(int& x:B[i]) cin>>x;
    }
    vector<int> ans=Det_A_Bz<998244353>()(A,B);
    For(i,0,n) cout<<ans[i]<<' ';; cout<<'\n';
    cerr<<"Time = "<<clock()<<" ms"<<endl;
    return 0;
}

// START TYPING IF YOU DON'T KNOW WHAT TO DO
// STOP TYPING IF YOU DON'T KNOW WHAT YOU'RE DOING
// CONTINUE, NON-STOPPING, FOR CHARLIEVINNIE

// Started Coding On: April 27 Thu, 11 : 04 : 39