結果
| 問題 |
No.1907 DETERMINATION
|
| コンテスト | |
| ユーザー |
 Qingliang Ou
|
| 提出日時 | 2023-10-20 10:45:42 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,041 bytes |
| コンパイル時間 | 2,229 ms |
| コンパイル使用メモリ | 180,404 KB |
| 実行使用メモリ | 17,920 KB |
| 最終ジャッジ日時 | 2024-09-20 06:20:44 |
| 合計ジャッジ時間 | 30,226 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 62 WA * 1 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define debug(x) cerr<<#x<<"="<<x<<endl
#define debugv(x) cerr<<#x<<" : ", ff(i,0,(x).size()) cerr<<(x)[i]<<(i==(x).size()-1?'\n':' ')
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define VI vector<int>
#define ll long long
#define ull unsigned ll
#define lll __int128
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define endl "\n"
template<class T>inline void read(T &x) {
x=0; char ch=getchar(); bool f=0;
for(;ch<'0'||ch>'9';ch=getchar()) f|=(ch=='-');
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+(ch^48);
if(f) x=-x;
}
template<class T, class... V>
inline void read(T &a, V&... b){read(a); read(b...);}
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 998244353;
inline ll Pow(ll x,ll y) {
ll ans = 1;
for(; y; y >>= 1, x = x * x % mod)
if(y & 1)
ans = ans * x % mod;
return ans;
}
inline ll Add(ll x,ll y) {
x += y;
return (x >= mod) ? x - mod : x;
}
inline ll Dec(ll x,ll y) {
x -= y;
return (x < 0) ? x + mod : x;
}
inline ll Mul(ll x,ll y) {
return 1ll * x * y % mod;
}
const int N=502;
struct matrix{
int n;
ll a[N][N];
matrix(){ n = 0; memset(a,0,sizeof(a));}
void clear(){ n = 0; memset(a,0,sizeof(a));}
void print() {
printf("%lld\n", n);
fo(i,1,n) {
fo(j,1,n) printf("%lld ", a[i][j]);
printf("\n");
}
}
};
namespace Mat {
static ll a[N][N],b[N][N+N],c[N][N],d[N][N];
static matrix B,C;
inline ll det(const matrix &A) { // 行列式
int n=A.n;
fo(i,1,n) fo(j,1,n) a[i][j]=A.a[i][j];
ll d=1,iv,tmp;
fo(i,1,n) {
int k=i;
fo(j,i+1,n) if(a[j][i]) {k=j; break;}
if(k!=i) {fo(j,i,n) swap(a[k][j],a[i][j]); d=(mod-d)%mod;}
if(!a[i][i]) return 0;
iv=Pow(a[i][i],mod-2);
fo(j,i+1,n) {
tmp=a[j][i]*iv%mod;
fo(k,i,n) a[j][k]=Dec(a[j][k],a[i][k]*tmp%mod);
}
d=d*a[i][i]%mod;
}
return d;
}
inline matrix inv(const matrix &A) {//求逆
int n=A.n;
fo(i,1,n) fo(j,1,n) b[i][j+n]=0,b[i][j]=A.a[i][j];
fo(i,1,n) b[i][i+n]=1;
ll iv,tmp;
fo(i,1,n) {
int k=n+1;
fo(j,i,n) if(b[j][i]) {k=j; break;}
if(k==n+1) continue;
if(k!=i) fo(j,1,n+n) swap(b[i][j],b[k][j]);
iv=Pow(b[i][i],mod-2);
fo(j,i+1,n) {
tmp=b[j][i]*iv%mod;
fo(k,i,n+n) b[j][k]=Dec(b[j][k],b[i][k]*tmp%mod);
}
}
fd(i,n,1) {
iv=Pow(b[i][i],mod-2);
fo(j,i,n+n) b[i][j]=b[i][j]*iv%mod;
fd(j,i-1,1)
if(b[j][i]) {
tmp=b[j][i];
fo(k,i,n+n) b[j][k]=Dec(b[j][k],b[i][k]*tmp%mod);
}
}
B.clear(); B.n = n;
fo(i,1,n) fo(j,1,n) B.a[i][j]=b[i][j+n];
return B;
}
int r(const matrix& A) { //求秩
int n=A.n;
fo(i,1,n) fo(j,1,n) a[i][j]=A.a[i][j];
int d=0;
ll iv,tmp;
fo(i,1,n) {
int k=n+1;
fo(j,i,n) if(a[j][i]) {k=j; break;}
if(k==n+1) continue;
d++;
if(k!=i) fo(j,i,n) swap(a[i][j],a[k][j]);
iv=Pow(a[i][i],mod-2);
fo(j,i+1,n) {
tmp=a[j][i]*iv%mod;
fo(k,i,n) a[j][k]=Dec(a[j][k],tmp*a[i][k]%mod);
}
}
return d;
}
static ll v[N],w[N];
inline bool ins(ll *v,int n,int id,ll *ans) {
fo(i,1,n) w[i]=0;
w[id]=1;
ll tmp;
fd(i,n,1)
if(v[i]) {
if(!c[i][i]) {
fd(j,i,1) c[i][j]=v[j];
fo(j,1,n) d[i][j]=w[j];
return 0;
}
tmp=Pow(c[i][i],mod-2)*v[i]%mod;
fd(j,i,1) v[j]=Dec(v[j],c[i][j]*tmp%mod);
fo(j,1,n) w[j]=Dec(w[j],d[i][j]*tmp%mod);
}
fo(i,1,n) ans[i]=w[i];
return 1;
}
inline void get_G(const matrix &A,ll *p) { //解齐次线性方程非零解
int n=A.n;
fo(i,1,n) fo(j,1,n) a[i][j]=A.a[i][j];
memset(c,0,sizeof(c)); memset(d,0,sizeof(d));
fo(i,1,n) {
fo(j,1,n) v[j]=a[j][i];
if(ins(v,n,i,p)) return;
}
}
inline matrix solve(const matrix &A) { //求所有代数余子式
int n=A.n;
int rank=r(A);
if(rank == n) {
ll d=det(A);
B=inv(A);
C.clear(); C.n = n;
fo(i,1,n) fo(j,1,n) C.a[i][j]=B.a[j][i]*d%mod;
return C;
}
else if(rank <= n-2) {
C.clear(); C.n = n;
return C;
}
else {
static ll p[N],q[N];
get_G(A,q);
fo(i,1,n) fo(j,1,n) B.a[j][i]=A.a[i][j];
get_G(B,p);
int c=0,r=0;
fo(i,1,n) if(q[i]) {c=i; break;}
fo(i,1,n) if(p[i]) {r=i; break;}
fo(i,1,n)
if(i!=r)
fo(j,1,n)
if(j!=c)
B.a[i-(i>r)][j-(j>c)]=A.a[i][j];
B.n = n - 1;
ll d=det(B);
C.clear(); C.n = n;
C.a[r][c]=((r+c)%2==1)?(mod-d)%mod:d;
ll iv=Pow(q[c]*p[r]%mod,mod-2);
fo(i,1,n)
fo(j,1,n)
C.a[i][j]=C.a[r][c]*iv%mod*p[i]%mod*q[j]%mod;
return C;
}
}
}
namespace Characteristic {
void HessenbergReduce(matrix &A) {
int n = A.n;
fo(i,1,n-2) {
int x = 0;
fo(j,i+1,n) if (A.a[j][i]) { x = j; break; }
if(!x) continue;
fo(j,1,n) swap(A.a[i+1][j], A.a[x][j]);
fo(j,1,n) swap(A.a[j][i+1], A.a[j][x]);
ll inv = Pow(A.a[i+1][i], mod - 2);
fo(j,i+2,n) {
ll t = A.a[j][i] * inv % mod;
fo(k,1,n) A.a[j][k] = Dec(A.a[j][k], Mul(t, A.a[i+1][k]));
fo(k,1,n) A.a[k][i+1] = Add(A.a[k][i+1], Mul(t, A.a[k][j]));
}
}
}
// 返回矩阵的特征多项式的系数，即 det(xI-A) 的各项系数
vector<ll> CharacteristicPolynomial(matrix A) {
int n = A.n;
HessenbergReduce(A);
vector<vector<ll>> p(n+1);
p[0] = {1};
ff(i,0,n) {
p[i+1].assign(i + 2, 0);
fo(j,0,i) p[i+1][j+1] = p[i][j];
fo(j,0,i) p[i+1][j] = Dec(p[i+1][j], Mul(A.a[i+1][i+1], p[i][j]));
ll tmp = 1;
fd(j,i-1,0) {
tmp = Mul(tmp, A.a[j+2][j+1]);
ll x = (mod - A.a[j+1][i+1]) * tmp % mod;
fo(k,0,j) p[i+1][k] = Add(p[i+1][k], Mul(x, p[j][k]));
}
}
return p[n];
}
vector<ll> detPoly(matrix A, matrix B) {
int n = A.n, x = 0;
ll invAB = 1;
fo(i,1,n) {
int y = 0;
fo(j,i,n) if (B.a[j][i]) { y = j; break; }
if (!y) {
++x;
if (x > n)
return vector<ll>(n+1, 0);
fo(j,1,i) {
ll v = B.a[j][i];
B.a[j][i] = 0;
fo(k,1,n) A.a[k][i] = Dec(A.a[k][i], Mul(v, A.a[k][j]));
}
fo(k,1,n) swap(A.a[k][i], B.a[k][i]);
-- i; continue;
}
if (y != i) {
invAB = mod - invAB;
fo(j,1,n) swap(A.a[i][j], A.a[y][j]);
fo(j,1,n) swap(B.a[i][j], B.a[y][j]);
}
invAB = Mul(invAB, B.a[i][i]);
ll inv = Pow(B.a[i][i], mod - 2);
fo(j,1,n) {
A.a[i][j] = Mul(A.a[i][j], inv);
B.a[i][j] = Mul(B.a[i][j], inv);
}
fo(j,1,n) if (j != i) {
ll tmp = B.a[j][i];
fo(k,1,n) {
A.a[j][k] = Dec(A.a[j][k], Mul(tmp, A.a[i][k]));
B.a[j][k] = Dec(B.a[j][k], Mul(tmp, B.a[i][k]));
}
}
}
fo(i,1,n)
fo(j,1,n)
A.a[i][j] = mod - A.a[i][j];
auto ans = CharacteristicPolynomial(A);
for (auto &x : ans) x = Mul(x, invAB);
ans.erase(ans.begin(), ans.begin() + x);
ans.resize(n + 1);
return ans;
}
}
int n;
matrix A, B;
int p[N];
int main() {
read(n);
A.n = B.n = n;
fo(i,1,n) fo(j,1,n) read(A.a[i][j]);
fo(i,1,n) fo(j,1,n) read(B.a[i][j]);
auto ans = Characteristic::detPoly(A, B);
fo(i,0,n) printf("%lld\n", ans[i]);
return 0;
}