#352015 (C++14) No.840 ほむほむほむら

提出ソース

結果

問題	No.840 ほむほむほむら
ユーザー	pazzle1230
提出日時	2019-06-14 22:36:17
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	309 ms / 4,000 ms
コード長	7,931 bytes
コンパイル時間	2,048 ms
コンパイル使用メモリ	178,892 KB
実行使用メモリ	6,820 KB
最終ジャッジ日時	2024-11-14 07:11:25
合計ジャッジ時間	4,318 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,820 KB
testcase_02	AC	8 ms 6,816 KB
testcase_03	AC	44 ms 6,820 KB
testcase_04	AC	2 ms 6,820 KB
testcase_05	AC	2 ms 6,816 KB
testcase_06	AC	3 ms 6,816 KB
testcase_07	AC	15 ms 6,820 KB
testcase_08	AC	78 ms 6,820 KB
testcase_09	AC	3 ms 6,816 KB
testcase_10	AC	2 ms 6,820 KB
testcase_11	AC	4 ms 6,816 KB
testcase_12	AC	23 ms 6,820 KB
testcase_13	AC	201 ms 6,820 KB
testcase_14	AC	27 ms 6,816 KB
testcase_15	AC	2 ms 6,816 KB
testcase_16	AC	5 ms 6,820 KB
testcase_17	AC	48 ms 6,820 KB
testcase_18	AC	256 ms 6,816 KB
testcase_19	AC	309 ms 6,820 KB
testcase_20	AC	2 ms 6,816 KB
testcase_21	AC	2 ms 6,816 KB
testcase_22	AC	6 ms 6,816 KB
testcase_23	AC	297 ms 6,820 KB
testcase_24	AC	6 ms 6,820 KB
testcase_25	AC	2 ms 6,820 KB
testcase_26	AC	7 ms 6,820 KB
testcase_27	AC	297 ms 6,816 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
  for(auto &e:u) fill_v<T>(e,v...);
}
template<::std::uint_fast64_t mod>
class ModInt{
private:
	using value_type = ::std::uint_fast64_t;
	value_type n;
public:
	ModInt() : n(0) {}
	ModInt(value_type n_) : n(n_ % mod) {}
	ModInt(const ModInt& m) : n(m.n) {}

	template<typename T>
	explicit operator T() const { return static_cast<T>(n); }
	value_type get() const { return n; }

	friend ::std::ostream& operator<<(::std::ostream &os, const ModInt<mod> &a) {
		return os << a.n;
	}

	friend ::std::istream& operator>>(::std::istream &is, ModInt<mod> &a) {
		value_type x;
		is >> x;
		a = ModInt<mod>(x);
		return is;
	}

	bool operator==(const ModInt& m) const { return n == m.n; }
	bool operator!=(const ModInt& m) const { return n != m.n; }
	ModInt& operator*=(const ModInt& m){ n = n * m.n % mod; return *this; }

	ModInt pow(value_type b) const{
		ModInt ans = 1, m = ModInt(*this);
		while(b){
			if(b & 1) ans *= m;
			m *= m;
			b >>= 1;
		}
		return ans;
	}

	ModInt inv() const { return (*this).pow(mod-2); }
	ModInt& operator+=(const ModInt& m){ n += m.n; n = (n < mod ? n : n - mod); return *this; }
	ModInt& operator-=(const ModInt& m){ n += mod - m.n; n = (n < mod ? n : n - mod); return *this; }
	ModInt& operator/=(const ModInt& m){ *this *= m.inv(); return *this; }
	ModInt operator+(const ModInt& m) const { return ModInt(*this) += m; }
	ModInt operator-(const ModInt& m) const { return ModInt(*this) -= m; }
	ModInt operator*(const ModInt& m) const { return ModInt(*this) *= m; }
	ModInt operator/(const ModInt& m) const { return ModInt(*this) /= m; }
	ModInt& operator++(){ n += 1; return *this; }
	ModInt& operator--(){ n -= 1; return *this; }
	ModInt operator++(int){
		ModInt old(n);
		n += 1;
		return old;
	}
	ModInt operator--(int){
		ModInt old(n);
		n -= 1;
		return old;
	}
	ModInt operator-() const { return ModInt(mod-n); }
};

template<typename T>
class Matrix{
private:
	using size_type = ::std::size_t;
	using Row = ::std::vector<T>;
	using Mat = ::std::vector<Row>;

	size_type R, C; // row, column
	Mat A;

	void add_row_to_another(size_type r1, size_type r2, const T k){ // Row(r1) += Row(r2)*k
		for(size_type i = 0;i < C;i++)
			A[r1][i] += A[r2][i]*k;
	}

	void scalar_multiply(size_type r, const T k){
		for(size_type i = 0;i < C;i++)
			A[r][i] *= k;
	}

	void scalar_division(size_type r, const T k){
		for(size_type i = 0;i < C;i++)
			A[r][i] /= k;
	}

public:
	Matrix(){}
	Matrix(size_type r, size_type c) : R(r), C(c), A(r, Row(c)) {}
	Matrix(const Mat &m) : R(m.size()), C(m[0].size()), A(m) {}
	Matrix(const Mat &&m) : R(m.size()), C(m[0].size()), A(m) {}
	Matrix(const Matrix<T> &m) : R(m.R), C(m.C), A(m.A) {}
	Matrix(const Matrix<T> &&m) : R(m.R), C(m.C), A(m.A) {}
	Matrix<T> &operator=(const Matrix<T> &m){
 		R = m.R; C = m.C; A = m.A;
		return *this;
	}
	Matrix<T> &operator=(const Matrix<T> &&m){
 		R = m.R; C = m.C; A = m.A;
		return *this;
	}
	static Matrix I(const size_type N){
		Matrix m(N, N);
		for(size_type i = 0;i < N;i++) m[i][i] = 1;
		return m;
	}

	const Row& operator[](size_type k) const& { return A.at(k); }
	Row& operator[](size_type k) & { return A.at(k); }
	Row operator[](size_type k) const&& { return ::std::move(A.at(k)); }

	size_type row() const { return R; } // the number of rows
	size_type column() const { return C; }

	T determinant(){
		assert(R == C);
		Mat tmp = A;
		T res = 1;
		for(size_type i = 0;i < R;i++){
			for(size_type j = i;j < R;j++){ // satisfy A[i][i] > 0
				if (A[j][i] != 0) {
					if (i != j) res *= -1;
					swap(A[j], A[i]);
					break;
				}
			}
			if (A[i][i] == 0) return 0;
			res *= A[i][i];
			scalar_division(i, A[i][i]);
			for(size_type j = i+1;j < R;j++){
				add_row_to_another(j, i, -A[j][i]);
			}
		}
		swap(tmp, A);
		return res;
	}

	Matrix inverse(){
		assert(R == C);
		assert(determinant() != 0);
		Matrix inv(Matrix::I(R)), tmp(*this);
		for(size_type i = 0;i < R;i++){
			for(size_type j = i;j < R;j++){
				if (A[j][i] != 0) {
					swap(A[j], A[i]);
					swap(inv[j], inv[i]);
					break;
				}
			}
			inv.scalar_division(i, A[i][i]);
			scalar_division(i, A[i][i]);
			for(size_type j = 0;j < R;j++){
				if(i == j) continue;
				inv.add_row_to_another(j, i, -A[j][i]);
				add_row_to_another(j, i, -A[j][i]);
			}
		}
		(*this) = tmp;
		return inv;
	}

	Matrix& operator+=(const Matrix &B){
		assert(column() == B.column() && row() == B.row());
		for(size_type i = 0;i < R;i++)
			for(size_type j = 0;j < C;j++)
				(*this)[i][j] += B[i][j];
		return *this;
	}

	Matrix& operator-=(const Matrix &B){
		assert(column() == B.column() && row() == B.row());
		for(size_type i = 0;i < R;i++)
			for(size_type j = 0;j < C;j++)
				(*this)[i][j] -= B[i][j];
		return *this;
	}

	Matrix& operator*=(const Matrix &B){
		assert(column() == B.row());
		Matrix M(R, B.column());
		for(size_type i = 0;i < R;i++) {
			for(size_type j = 0;j < B.column();j++) {
				M[i][j] = 0;
				for(size_type k = 0;k < C;k++) {
					M[i][j] += (*this)[i][k] * B[k][j];
				}
			}
		}
		swap(M, *this);
		return *this;
	}

	Matrix& operator/=(const Matrix &B){
		assert(C == B.row());
		Matrix M(B);
		(*this) *= M.inverse();
		return *this;
	}

	Matrix operator+(const Matrix &B) const { return (Matrix(*this) += B); }
	Matrix operator-(const Matrix &B) const { return (Matrix(*this) -= B); }
	Matrix operator*(const Matrix &B) const { return (Matrix(*this) *= B); }
	Matrix operator/(const Matrix &B) const { return (Matrix(*this) /= B); }

	bool operator==(const Matrix &B) const {
		if (column() != B.column() || row() != B.row()) return false;
		for(size_type i = 0;i < row();i++)
			for(size_type j = 0;j < column();j++)
				if ((*this)[i][j] != B[i][j]) return false;
		return true;
	}
	bool operator!=(const Matrix &B) const { return !((*this) == B); }

	Matrix pow(size_type k){
		assert(R == C);
		Matrix M(Matrix::I(R));
		while(k){
			if (k & 1) M *= (*this);
			k >>= 1;
			(*this) *= (*this);
		}
		A.swap(M.A);
		return *this;
	}

	friend ::std::ostream &operator<<(::std::ostream &os, Matrix &p){
		for(size_type i = 0;i < p.row();i++){
			for(size_type j = 0;j < p.column();j++){
				os << p[i][j] << " ";
			}
			os << ::std::endl;
		}
		return os;
	}
};
constexpr int64 mod = 998244353;
using Mint = ModInt<mod>;
using Mat = Matrix<Mint>;

int64 N, K;
inline int64 to_idx(int64 a, int64 b, int64 c) {
	return a*K*K+b*K+c;
}

int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> N >> K;
	Mat m(K*K*K, K*K*K), b(K*K*K, 1);
	REP(i, K) {
		REP(j, K) {
			REP(k, K) {
				m[to_idx(i, j, (k+j)%K)][to_idx(i, j, k)] += 1;
				m[to_idx(i, (j+i)%K, k)][to_idx(i, j, k)] += 1;
				m[to_idx((i+1)%K, j, k)][to_idx(i, j, k)] += 1;
			}
		}
	}
	m.pow(N);
	b[to_idx(0, 0, 0)][0] = 1;
	Mat a = m * b;
	Mint res = 0;
	REP(i, K) {
		REP(j, K) {
			res += a[to_idx(i, j, 0)][0];
		}
	}
	cout << res << endl;
}

yukicoder

結果

テストケース

ソースコード