QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#100635 | #59. Determinant of A+Bz | CharlieVinnie | Judging | / | / | C++17 | 4.1kb | 2023-04-27 14:39:02 | 2024-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: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: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