結果
| 問題 |
No.840 ほむほむほむら
|
| コンテスト | |
| ユーザー |
 MarcusAureliusAntoninus
|
| 提出日時 | 2019-06-14 23:04:20 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 256 ms / 4,000 ms |
| コード長 | 5,318 bytes |
| コンパイル時間 | 2,290 ms |
| コンパイル使用メモリ | 206,184 KB |
| 最終ジャッジ日時 | 2025-01-07 04:36:32 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 25 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:203:19: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘int64_t*’ {aka ‘long int*’} [-Wformat=]
203 | scanf("%lld%d", &N, &K);
| ~~~^ ~~
| | |
| | int64_t* {aka long int*}
| long long int*
| %ld
main.cpp:223:20: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘int64_t’ {aka ‘long int’} [-Wformat=]
223 | printf("%lld\n", (int64_t)ans_num);
| ~~~^ ~~~~~~~~~~~~~~~~
| | |
| | int64_t {aka long int}
| long long int
| %ld
main.cpp:203:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
203 | scanf("%lld%d", &N, &K);
| ~~~~~^~~~~~~~~~~~~~~~~~
ソースコード
#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;
}