#920725 (C++14) No.1907 DETERMINATION

提出ソース

結果

問題	No.1907 DETERMINATION
ユーザー	Qingliang Ou
提出日時	2023-10-20 10:49:42
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	762 ms / 4,000 ms
コード長	8,093 bytes
コンパイル時間	2,023 ms
コンパイル使用メモリ	181,472 KB
実行使用メモリ	18,748 KB
最終ジャッジ日時	2023-10-20 10:50:10
合計ジャッジ時間	27,412 ms
ジャッジサーバーID （参考情報）	judge12 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	9 ms 18,544 KB
testcase_01	AC	9 ms 18,544 KB
testcase_02	AC	7 ms 16,576 KB
testcase_03	AC	8 ms 18,548 KB
testcase_04	AC	9 ms 18,548 KB
testcase_05	AC	9 ms 18,548 KB
testcase_06	AC	9 ms 18,548 KB
testcase_07	AC	208 ms 18,744 KB
testcase_08	AC	86 ms 18,736 KB
testcase_09	AC	146 ms 18,744 KB
testcase_10	AC	503 ms 18,748 KB
testcase_11	AC	176 ms 16,580 KB
testcase_12	AC	496 ms 18,748 KB
testcase_13	AC	468 ms 18,744 KB
testcase_14	AC	424 ms 18,748 KB
testcase_15	AC	97 ms 18,744 KB
testcase_16	AC	36 ms 18,636 KB
testcase_17	AC	468 ms 18,744 KB
testcase_18	AC	326 ms 18,744 KB
testcase_19	AC	16 ms 18,584 KB
testcase_20	AC	469 ms 18,744 KB
testcase_21	AC	47 ms 18,668 KB
testcase_22	AC	416 ms 16,580 KB
testcase_23	AC	553 ms 18,744 KB
testcase_24	AC	154 ms 18,744 KB
testcase_25	AC	9 ms 18,548 KB
testcase_26	AC	511 ms 18,748 KB
testcase_27	AC	612 ms 18,748 KB
testcase_28	AC	613 ms 18,748 KB
testcase_29	AC	608 ms 18,748 KB
testcase_30	AC	9 ms 18,548 KB
testcase_31	AC	518 ms 18,748 KB
testcase_32	AC	503 ms 18,748 KB
testcase_33	AC	506 ms 18,748 KB
testcase_34	AC	509 ms 18,748 KB
testcase_35	AC	9 ms 18,548 KB
testcase_36	AC	9 ms 18,548 KB
testcase_37	AC	9 ms 18,548 KB
testcase_38	AC	508 ms 18,748 KB
testcase_39	AC	506 ms 18,748 KB
testcase_40	AC	729 ms 18,748 KB
testcase_41	AC	510 ms 18,748 KB
testcase_42	AC	731 ms 18,748 KB
testcase_43	AC	762 ms 18,748 KB
testcase_44	AC	575 ms 18,748 KB
testcase_45	AC	614 ms 18,748 KB
testcase_46	AC	503 ms 18,748 KB
testcase_47	AC	501 ms 18,748 KB
testcase_48	AC	504 ms 18,748 KB
testcase_49	AC	533 ms 18,748 KB
testcase_50	AC	505 ms 18,748 KB
testcase_51	AC	507 ms 18,748 KB
testcase_52	AC	8 ms 16,576 KB
testcase_53	AC	518 ms 16,580 KB
testcase_54	AC	514 ms 16,580 KB
testcase_55	AC	8 ms 16,576 KB
testcase_56	AC	526 ms 16,580 KB
testcase_57	AC	520 ms 16,580 KB
testcase_58	AC	421 ms 18,748 KB
testcase_59	AC	320 ms 18,748 KB
testcase_60	AC	321 ms 18,748 KB
testcase_61	AC	408 ms 18,748 KB
testcase_62	AC	321 ms 18,748 KB
testcase_63	AC	508 ms 18,748 KB
testcase_64	AC	10 ms 18,544 KB
testcase_65	AC	9 ms 18,544 KB
testcase_66	AC	9 ms 18,544 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード