結果

問題 No.1907 DETERMINATION
ユーザー Qingliang OuQingliang Ou
提出日時 2023-10-20 10:49:42
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 715 ms / 4,000 ms
コード長 8,093 bytes
コンパイル時間 2,165 ms
コンパイル使用メモリ 182,392 KB
実行使用メモリ 19,400 KB
最終ジャッジ日時 2024-09-20 06:25:01
合計ジャッジ時間 27,671 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 8 ms
18,756 KB
testcase_01 AC 9 ms
17,728 KB
testcase_02 AC 7 ms
15,556 KB
testcase_03 AC 8 ms
17,860 KB
testcase_04 AC 8 ms
18,112 KB
testcase_05 AC 8 ms
17,528 KB
testcase_06 AC 8 ms
17,732 KB
testcase_07 AC 194 ms
17,768 KB
testcase_08 AC 84 ms
18,372 KB
testcase_09 AC 141 ms
17,732 KB
testcase_10 AC 473 ms
19,400 KB
testcase_11 AC 167 ms
15,552 KB
testcase_12 AC 473 ms
18,576 KB
testcase_13 AC 453 ms
17,900 KB
testcase_14 AC 404 ms
18,372 KB
testcase_15 AC 93 ms
18,372 KB
testcase_16 AC 35 ms
18,628 KB
testcase_17 AC 455 ms
18,376 KB
testcase_18 AC 315 ms
18,780 KB
testcase_19 AC 15 ms
18,372 KB
testcase_20 AC 443 ms
18,884 KB
testcase_21 AC 45 ms
18,504 KB
testcase_22 AC 397 ms
15,680 KB
testcase_23 AC 526 ms
18,244 KB
testcase_24 AC 144 ms
17,732 KB
testcase_25 AC 9 ms
17,992 KB
testcase_26 AC 481 ms
18,888 KB
testcase_27 AC 574 ms
19,008 KB
testcase_28 AC 581 ms
17,864 KB
testcase_29 AC 580 ms
19,012 KB
testcase_30 AC 9 ms
18,116 KB
testcase_31 AC 487 ms
17,856 KB
testcase_32 AC 471 ms
18,628 KB
testcase_33 AC 478 ms
18,760 KB
testcase_34 AC 495 ms
18,760 KB
testcase_35 AC 9 ms
17,360 KB
testcase_36 AC 7 ms
17,992 KB
testcase_37 AC 9 ms
17,376 KB
testcase_38 AC 476 ms
19,268 KB
testcase_39 AC 485 ms
17,992 KB
testcase_40 AC 705 ms
17,988 KB
testcase_41 AC 487 ms
18,372 KB
testcase_42 AC 715 ms
19,016 KB
testcase_43 AC 708 ms
18,368 KB
testcase_44 AC 545 ms
18,372 KB
testcase_45 AC 619 ms
17,864 KB
testcase_46 AC 484 ms
18,372 KB
testcase_47 AC 483 ms
18,368 KB
testcase_48 AC 482 ms
18,116 KB
testcase_49 AC 517 ms
18,256 KB
testcase_50 AC 477 ms
18,368 KB
testcase_51 AC 476 ms
17,988 KB
testcase_52 AC 7 ms
15,940 KB
testcase_53 AC 491 ms
15,936 KB
testcase_54 AC 493 ms
15,360 KB
testcase_55 AC 7 ms
15,684 KB
testcase_56 AC 490 ms
15,428 KB
testcase_57 AC 506 ms
16,320 KB
testcase_58 AC 402 ms
18,504 KB
testcase_59 AC 305 ms
17,776 KB
testcase_60 AC 302 ms
18,756 KB
testcase_61 AC 388 ms
18,248 KB
testcase_62 AC 311 ms
19,264 KB
testcase_63 AC 485 ms
17,732 KB
testcase_64 AC 9 ms
17,736 KB
testcase_65 AC 8 ms
18,372 KB
testcase_66 AC 8 ms
18,120 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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) % mod;
                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]) % mod;
        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]), A.a[i][j] %= mod;
    fo(i,1,n) fo(j,1,n) read(B.a[i][j]), B.a[i][j] %= mod;
    auto ans = Characteristic::detPoly(A, B);
    fo(i,0,n) printf("%lld\n", ans[i]);
    return 0;
}
0