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

提出ソース

結果

問題	No.1907 DETERMINATION
ユーザー	TKTYI
提出日時	2022-04-15 22:39:15
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	10,754 bytes
コンパイル時間	3,894 ms
コンパイル使用メモリ	236,176 KB
実行使用メモリ	7,752 KB
最終ジャッジ日時	2023-08-26 08:21:11
合計ジャッジ時間	11,001 ms
ジャッジサーバーID （参考情報）	judge14 / judge11

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,376 KB
testcase_01	AC	2 ms 4,376 KB
testcase_02	AC	1 ms 4,376 KB
testcase_03	TLE	-
testcase_04	--	-
testcase_05	--	-
testcase_06	--	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
testcase_39	--	-
testcase_40	--	-
testcase_41	--	-
testcase_42	--	-
testcase_43	--	-
testcase_44	--	-
testcase_45	--	-
testcase_46	--	-
testcase_47	--	-
testcase_48	--	-
testcase_49	--	-
testcase_50	--	-
testcase_51	--	-
testcase_52	--	-
testcase_53	--	-
testcase_54	--	-
testcase_55	--	-
testcase_56	--	-
testcase_57	--	-
testcase_58	--	-
testcase_59	--	-
testcase_60	--	-
testcase_61	--	-
testcase_62	--	-
testcase_63	--	-
testcase_64	--	-
testcase_65	--	-
testcase_66	--	-

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

ソースコード

raw source code

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
typedef long long int ll;
typedef long double ld;
#define FOR(i,l,r) for(ll i=l;i<r;i++)
#define REP(i,n) FOR(i,0,n)
#define RFOR(i,l,r) for(ll i=r-1;i>=l;i--)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(x) x.begin(),x.end()
#define PA pair<ll,ll>
#define F first
#define S second
#define BS(A,x) binary_search(ALL(A),x)
#define LB(A,x) (ll)(lower_bound(ALL(A),x)-A.begin())
#define UB(A,x) (ll)(upper_bound(ALL(A),x)-A.begin())
#define COU(A,x) (UB(A,x)-LB(A,x))
template<typename T>using min_priority_queue=priority_queue<T,vector<T>,greater<T>>;
//using mint=modint1000000007;
using mint=modint998244353;
void chmax(ll&a,ll b){a=max(a,b);}
void chmin(ll&a,ll b){a=min(a,b);}
void print(vector<ll>A){REP(i,A.size()){if(i)cout<<" ";cout<<A[i];}cout<<endl;}
ld dist(ld x1,ld y1,ld x2,ld y2){return sqrtl((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
namespace MatrixLib {
    class print_format_error: public std::exception {
        virtual const char* what() const noexcept { return "Error: print() method cannot print these values because of unsupported!"; }
    };
    class matrix_product_error: public std::exception {
        virtual const char* what() const noexcept { return "Error: Impossible to calculate matrix product!"; }
    };
    class determinant_error: public std::exception {
        virtual const char* what() const noexcept { return "Error: Impossible to calculate determinant!"; }
    };
    class inversion_error: public std::exception {
        virtual const char* what() const noexcept { return "Error: Impossible to calculate inversion!"; }
    };


    /*** 二次元行列のライブラリMatrix ***/
    template <typename T>
    class Matrix {
        private:
            vector<vector<T>> A;

            T __cofactor(const vector<vector<T>>& coA) const {
                /* 各余因子の計算を再帰的にする */
                if (coA.size() == 1) return coA[0][0];
                if (coA.size() == 2) {
                    return coA[0][0]*coA[1][1]-coA[0][1]*coA[1][0];
                }

                T res = 0;
                for (int col2=0; col2<coA.size(); col2++) {
                    vector<vector<T>> cocoA(coA.size()-1);
                    for (int row=1; row<coA.size(); row++) {
                        for (int col=0; col<coA.size(); col++) {
                            if (col2==col) continue;
                            cocoA[row-1].emplace_back(coA[row][col]);
                        }
                    }
                    if (!(col2&1)) res += coA[0][col2] * __cofactor(cocoA);
                    else res -= coA[0][col2] * __cofactor(cocoA);
                }
                return res;
            }
        public:
            size_t row;
            size_t col;
            Matrix(size_t row=1, size_t col=1) {
                this->row = row;
                this->col = col;
                this->A.resize(row);
                for(size_t i=0; i<row; i++) this->A[i].resize(col);
            }

            vector<T>& operator[](const size_t i) {
                return this->A[i];
            }

            Matrix& operator+=(Matrix other) {
                for(size_t i=0; i<this->row; i++) {
                    for(size_t j=0; j<this->col; j++) {
                        this->A[i][j] += other[i][j];
                    }
                }
                return *this;
            }
            Matrix operator+(const Matrix other) const {
                return Matrix(*this) += other;
            }
            Matrix& operator+=(const double a) {
                /* 各要素にaを足す */
                for (size_t i=0; i<this->row; i++) {
                    for (size_t j=0; j<this->col; j++) {
                        this->A[i][j] += a;
                    }
                }
                return *this;
            }
            Matrix operator+(const double a) const {
                return Matrix(*this) += a;
            }

            Matrix& operator-=(Matrix other) {
                for(size_t i=0; i<this->row; i++) {
                    for(size_t j=0; j<this->col; j++) {
                        this->A[i][j] -= other[i][j];
                    }
                }
                return *this;
            }
            Matrix operator-(const Matrix other) const {
                return Matrix(*this) -= other;
            }
            Matrix operator-() const {
                Matrix res(this->row, this->col);
                for (size_t i=0; i<this->row; i++) {
                    for (size_t j=0; j<this->col; j++) {
                        res[i][j] = -this->A[i][j];
                    }
                }
                return res;
            }
            Matrix& operator-=(const double a) {
                /* 各要素にaを引く */
                for (size_t i=0; i<this->row; i++) {
                    for (size_t j=0; j<this->col; j++) {
                        this->A[i][j] -= a;
                    }
                }
                return *this;
            }
            Matrix operator-(const double a) const {
                return Matrix(*this) -= a;
            }

            Matrix& operator*=(Matrix other) {
                /* NxN行列 x NxN行列 の積を求める */
                if (!(this->row==this->col && other.row==other.col && this->row==other.row)) throw matrix_product_error();

                vector<vector<T>> res(this->row, vector<T>(this->col, 0));
                for(size_t i=0; i<other.row; i++) {
                    for (size_t j=0; j<this->col; j++) {
                        for (size_t k=0; k<this->col; k++) {
                            res[i][j] += this->A[i][k]*other[k][j];
                        }
                    }
                }
                this->A = res;
                return *this;
            }
            Matrix operator*(Matrix other) const {
                /* ixk行列 * kxj行列 の積を求める */
                if (this->col!=other.row) throw matrix_product_error();

                Matrix<T> res(this->row, other.col);
                for (size_t i=0; i<this->row; i++) {
                    for (size_t j=0; j<other.col; j++) {
                        for (size_t k=0; k<this->col; k++) {
                            res[i][j] += this->A[i][k]*other[k][j];
                        }
                    }
                }
                return res;
            }

            Matrix& operator*=(const double a) {
                /* 各要素にaをかける */
                for (size_t i=0; i<this->row; i++) {
                    for (size_t j=0; j<this->col; j++) {
                        this->A[i][j] *= a;
                    }
                }
                return *this;
            }
            Matrix operator*(const double a) const {
                return Matrix(*this) *= a;
            }

            void print() {
                /* 行列の状態を表示する */
                string format;
                if (typeid(T)==typeid(int)) format = "%*d"s;
                else if (typeid(T)==typeid(unsigned int) || typeid(T)==typeid(unsigned short)) format = "%*u"s;
                else if (typeid(T)==typeid(long)) format = "%*ld"s;
                else if (typeid(T)==typeid(unsigned long)) format = "%*lu"s;
                else if (typeid(T)==typeid(long long)) format = "%*lld"s;
                else if (typeid(T)==typeid(unsigned long long)) format = "%*llu"s;
                else if (typeid(T)==typeid(short)) format = "%*f"s;
                else if (typeid(T)==typeid(double)) format = "%*lf"s;
                else if (typeid(T)==typeid(long double)) format = "%*LF"s;
                else throw print_format_error();

                int len = 0;
                for (size_t i=0; i<this->row; i++) {
                    for (size_t j=0; j<this->col; j++) {
                        string str = to_string(this->A[i][j]);
                        len = max(len, (int)str.size());
                    }
                }

                printf("[[");
                for (size_t i=0; i<this->row; i++) {
                    for (size_t j=0; j<this->col; j++) {
                        printf(format.c_str(), len, this->A[i][j]);
                        if (j!=this->col-1) printf(", ");
                        else printf("]");
                    }
                    if (i!=this->row-1) printf(",\n  ");
                    else printf("]\n");
                }
            }

            T det() const {
                /* 行列式を計算して返す */
                if (this->row!=this->col) throw determinant_error();

                return this->__cofactor(this->A);
            }

            Matrix dot(const Matrix B) const {
                /* ドット積（内積）計算をする */
                return Matrix(*this) * B;
            }

            Matrix inv() const {
                /* 逆行列を返す（掃き出し法） */
                if (!(this->row==this->col)) throw inversion_error();

                size_t N = this->row;
                Matrix<T> A = *this;
                Matrix<T> invA(N, N);
                for (size_t i=0; i<N; i++) {
                    for (size_t j=0; j<N; j++) {
                        invA[i][j] = (i==j) ? 1 : 0;
                    }
                }

                for (size_t i=0; i<N; i++) {
                    T buf = 1/A[i][i];
                    for (size_t j=0; j<N; j++) {
                        A[i][j] *= buf;
                        invA[i][j] *= buf;
                    }

                    for (size_t j=0; j<N; j++) {
                        if (i!=j) {
                            buf = A[j][i];
                            for (size_t k=0; k<N; k++) {
                                A[j][k] -= A[i][k]*buf;
                                invA[j][k] -= invA[i][k]*buf;
                            }
                        }
                    }
                }

                return invA;
            }
    };
}
using namespace MatrixLib;
int main(){
  ll N;cin>>N;
  Matrix<mint>M0(N,N),M1(N,N);
  REP(i,N)REP(j,N){ll x;cin>>x;M0[i][j]=x;}
  REP(i,N)REP(j,N){ll x;cin>>x;M1[i][j]=x;}
  vector<mint>A(N+1);
  REP(x,N+1){
    Matrix<mint>M(N,N);
    REP(i,N)REP(j,N)M[i][j]=M0[i][j]+M1[i][j]*x;
    A[x]=M.det();
  }
  vector<mint>ans(N+1),K(N+1,1);
  FOR(i,1,N+1)K[i]=i*K[i-1];
  REP(i,N+1){
    vector<mint>DP(N+1);
    DP[0]=1;
    REP(j,N+1)if(i!=j){
      RREP(k,N)DP[k+1]=DP[k]-j*DP[k+1];
      DP[0]=-j*DP[0];
    }
    REP(j,N+1){
      if((N-i)%2)ans[j]-=DP[j]*A[i]/K[N-i]/K[i];
      else ans[j]+=DP[j]*A[i]/K[N-i]/K[i];
    }
  }
  REP(i,N+1)cout<<ans[i].val()<<endl;
  return 0;
}

yukicoder

結果

テストケース

ソースコード