結果
| 問題 |
No.1907 DETERMINATION
|
| コンテスト | |
| ユーザー |
 TKTYI
|
| 提出日時 | 2022-04-15 22:39:15 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 10,754 bytes |
| コンパイル時間 | 4,883 ms |
| コンパイル使用メモリ | 238,536 KB |
| 実行使用メモリ | 141,760 KB |
| 最終ジャッジ日時 | 2024-12-25 01:44:12 |
| 合計ジャッジ時間 | 315,036 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 TLE * 1 |
| other | AC * 3 TLE * 60 |
ソースコード
#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;
}