#352098 (C++17) No.840 ほむほむほむら

提出ソース

結果

問題	No.840 ほむほむほむら
ユーザー	MarcusAureliusAntoninus
提出日時	2019-06-14 23:04:20
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	224 ms / 4,000 ms
コード長	5,318 bytes
コンパイル時間	2,477 ms
コンパイル使用メモリ	214,064 KB
実行使用メモリ	6,820 KB
最終ジャッジ日時	2024-11-14 12:58:42
合計ジャッジ時間	4,614 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	6 ms 6,820 KB
testcase_03	AC	32 ms 6,816 KB
testcase_04	AC	2 ms 6,816 KB
testcase_05	AC	2 ms 6,820 KB
testcase_06	AC	3 ms 6,816 KB
testcase_07	AC	11 ms 6,816 KB
testcase_08	AC	56 ms 6,816 KB
testcase_09	AC	3 ms 6,816 KB
testcase_10	AC	2 ms 6,820 KB
testcase_11	AC	3 ms 6,816 KB
testcase_12	AC	16 ms 6,816 KB
testcase_13	AC	144 ms 6,816 KB
testcase_14	AC	19 ms 6,816 KB
testcase_15	AC	2 ms 6,816 KB
testcase_16	AC	4 ms 6,816 KB
testcase_17	AC	34 ms 6,816 KB
testcase_18	AC	182 ms 6,816 KB
testcase_19	AC	224 ms 6,816 KB
testcase_20	AC	2 ms 6,816 KB
testcase_21	AC	2 ms 6,816 KB
testcase_22	AC	4 ms 6,816 KB
testcase_23	AC	210 ms 6,820 KB
testcase_24	AC	5 ms 6,820 KB
testcase_25	AC	2 ms 6,820 KB
testcase_26	AC	6 ms 6,820 KB
testcase_27	AC	213 ms 6,816 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>

////////////
// ModInt //
////////////

// 四則演算の最も左に存在する値がModIntでなければキャストでバグる
// 例えばx = mint * 1000;やx = ModInt(1000) * mint;はいいがx = 1000 * mint;は駄目。
template<int64_t mod_ = 1'000'000'007>
class ModInt {
private:
	int64_t integer_;

public:
	constexpr ModInt(const int64_t initial_number = 0)
		: integer_(initial_number){}
	
	// 四則演算
	constexpr ModInt operator+(const ModInt& operand) const
	{
		ModInt ret{this->integer_ + operand.integer_};
		if (ret.integer_ >= mod_)
			ret.integer_ -= mod_;
		return ret;
	}
	constexpr ModInt operator-(const ModInt& operand) const
	{
		ModInt ret{this->integer_ - operand.integer_};
		if (ret.integer_ < 0)
			ret.integer_ += mod_;
		return ret;
	}
	constexpr ModInt operator*(const ModInt& operand) const
	{
		return {this->integer_ * operand.integer_ % mod_};
	}
	constexpr ModInt operator/(const ModInt& operand) const
	{
		return *this * (operand ^ (mod_ - 2));
	}

	// 累乗
	constexpr ModInt operator^(const int64_t operand) const
	{
		ModInt ret{1}, pow_ope{this->integer_};
		for (int64_t pow{operand}; pow > 0; pow >>= 1)
		{
			if (pow & 1) ret *= pow_ope;
			pow_ope *= pow_ope;
		}
		return ret;
	}

	// 代入
	constexpr ModInt& operator=(const ModInt& operand)
	{
		this->integer_ = operand.integer_;
		return *this;
	}
	constexpr ModInt& operator+=(const ModInt& operand)
	{
		*this = *this + operand;
		return *this;
	}
	constexpr ModInt& operator-=(const ModInt& operand)
	{
		*this = *this - operand;
		return *this;
	}
	constexpr ModInt& operator*=(const ModInt& operand)
	{
		*this = *this * operand;
		return *this;
	}
	constexpr ModInt& operator/=(const ModInt& operand)
	{
		*this = *this / operand;
		return *this;
	}

	// その他
	constexpr operator int64_t() { return integer_; }
};

////////////
// 行列型 //
///////////

// 加算、減算、乗算をもつM×N型行列
// M=Nで環をつくる
template<typename T = int64_t>
class Matrix {
private:
	using RowVector = std::vector<T>;

	std::vector<RowVector> container_;

public:
	const int M, N;

	Matrix(const int row_size, const int column_size)
		: M(row_size), N(column_size), container_(row_size, RowVector(column_size)){}
	// ムーブコンストラクタ
	Matrix(Matrix<T>&& mat)
		: M(mat.M), N(mat.N), container_(std::move(mat.container_)){}
	// コピーコンストラクタ
	Matrix(Matrix<T>& mat)
		: M(mat.M), N(mat.N), container_(mat.container_){}

	// 要素アクセス
	RowVector& operator[](const int r) { return container_[r]; }
	const RowVector& operator[](const int r) const { return container_[r]; }
	// イテレータ
	typename decltype(container_)::iterator begin(){ return container_.begin(); }
	typename decltype(container_)::iterator end(){ return container_.end(); }

	// 環の演算
	Matrix<T> operator+(const Matrix<T>& mat) const
	{
		Matrix<T> ret{*this};
		for (int r_i{}; r_i < M; r_i++)
			for (int c_i{}; c_i < N; c_i++)
				ret[r_i][c_i] += mat[r_i][c_i];
		return std::move(ret);
	}
	Matrix<T> operator-(const Matrix<T>& mat) const
	{
		Matrix<T> ret{*this};
		for (int r_i{}; r_i < M; r_i++)
			for (int c_i{}; c_i < N; c_i++)
				ret[r_i][c_i] -= mat[r_i][c_i];
		return std::move(ret);
	}
	Matrix<T> operator*(const Matrix<T>& mat) const
	{
		Matrix<T> ret(this->M, mat.N);
		for (int r_i{}; r_i < this->M; r_i++)
			for (int c_i{}; c_i < mat.N; c_i++)
				for (int l_i{}; l_i < this->N; l_i++)
					ret[r_i][c_i] += (*this)[r_i][l_i] * mat[l_i][c_i];
		return std::move(ret);
	}
	std::vector<T> operator*(const std::vector<T>& vec) const
	{
		std::vector<T> ret(M);
		for (int r_i{}; r_i < M; r_i++)
			for (int c_i{}; c_i < N; c_i++)
				ret[r_i] += (*this)[r_i][c_i] * vec[c_i];
		return std::move(ret);
	}

	// 累乗
	Matrix<T> operator^(const int64_t index)
	{
		Matrix<T> ret(M, M), pow(*this);
		for (int i{}; i < M; i++)
			ret[i][i] = 1ll;
		for (int64_t i{index}; i > 0; i >>= 1)
		{
			if (i & 1)
				ret *= pow;
			pow *= pow;
		}
		return std::move(ret);
	}

	// 代入演算子
	Matrix<T>& operator=(const Matrix& mat)
	{
		this->container_ = mat.container_;
		return *this;
	}	
	Matrix<T>& operator+=(const Matrix& mat)
	{
		*this = *this + mat;
		return *this;
	}
	Matrix<T>& operator-=(const Matrix& mat)
	{
		*this = *this - mat;
		return *this;
	}
	Matrix<T>& operator*=(const Matrix& mat)
	{
		*this = *this * mat;
		return *this;
	}
};

int64_t N;
int K;

int calcNum(std::array<int, 3> arr)
{
	int ret{};
	for (int i{}; i < 3; i++)
		ret = ret * K + arr[i];
	return ret;
}

int main()
{
	scanf("%lld%d", &N, &K);
	using Mint = ModInt<998244353>;
	using Mat = Matrix<Mint>;
	// ほ度む度ら度
	Mat homuMat(K * K * K, K * K * K);
	for (int ho{}; ho < K; ho++)
		for (int mu{}; mu < K; mu++)
			for (int ra{}; ra < K; ra++)
			{
				homuMat[calcNum({(ho + 1) % K, mu, ra})][calcNum({ho, mu, ra})] += 1;
				homuMat[calcNum({ho, (mu + ho) % K, ra})][calcNum({ho, mu, ra})] += 1;
				homuMat[calcNum({ho, mu, (ra + mu) % K})][calcNum({ho, mu, ra})] += 1;
			}
	std::vector<Mint> ansVec(K * K * K);
	ansVec[0] = 1;
	ansVec = (homuMat ^ N) * ansVec;
	Mint ans_num;
	for (int i{}; i < K; i++)
		for (int j{}; j < K; j++)
			ans_num += ansVec[calcNum({i, j, 0})];
	printf("%lld\n", (int64_t)ans_num);

	return 0;
}

yukicoder

結果

テストケース

ソースコード