結果

問題 No.2807 Have Another Go (Easy)
ユーザー rniya
提出日時 2024-07-12 23:22:46
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 235 ms / 3,000 ms
コード長 8,076 bytes
コンパイル時間 2,855 ms
コンパイル使用メモリ 254,328 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-12 23:22:57
合計ジャッジ時間 10,148 ms
ジャッジサーバーID
(参考情報)
judge6 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void(0)
#endif
template <class T> std::istream& operator>>(std::istream& is, std::vector<T>& v) {
for (auto& e : v) {
is >> e;
}
return is;
}
template <class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
for (std::string_view sep = ""; const auto& e : v) {
os << std::exchange(sep, " ") << e;
}
return os;
}
template <class T, class U = T> bool chmin(T& x, U&& y) {
return y < x and (x = std::forward<U>(y), true);
}
template <class T, class U = T> bool chmax(T& x, U&& y) {
return x < y and (x = std::forward<U>(y), true);
}
template <class T> void mkuni(std::vector<T>& v) {
std::ranges::sort(v);
auto result = std::ranges::unique(v);
v.erase(result.begin(), result.end());
}
template <class T> int lwb(const std::vector<T>& v, const T& x) {
return std::distance(v.begin(), std::ranges::lower_bound(v, x));
}
#include <atcoder/modint>
template <typename T, int N> struct SquareMatrix {
std::array<std::array<T, N>, N> A;
SquareMatrix() : A() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
A[i][j] = T(0);
}
}
}
int size() const { return N; }
inline const std::array<T, N>& operator[](int i) const { return A[i]; }
inline std::array<T, N>& operator[](int i) { return A[i]; }
static SquareMatrix identity() {
SquareMatrix res;
for (int i = 0; i < N; i++) res[i][i] = 1;
return res;
}
SquareMatrix& operator+=(const SquareMatrix& B) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
(*this)[i][j] += B[i][j];
}
}
return *this;
}
SquareMatrix& operator-=(const SquareMatrix& B) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
(*this)[i][j] -= B[i][j];
}
}
return *this;
}
SquareMatrix& operator*=(const SquareMatrix& B) {
std::array<std::array<T, N>, N> C;
for (int i = 0; i < N; i++) {
for (int k = 0; k < N; k++) {
for (int j = 0; j < N; j++) {
C[i][j] += (*this)[i][k] * B[k][j];
}
}
}
std::swap(A, C);
return *this;
}
SquareMatrix& operator*=(const T& v) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
(*this)[i][j] *= v;
}
}
return *this;
}
SquareMatrix& operator/=(const T& v) {
T inv = T(1) / v;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
(*this)[i][j] *= inv;
}
}
return *this;
}
SquareMatrix operator-() const {
SquareMatrix res;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
res[i][j] = -(*this)[i][j];
}
}
return res;
}
SquareMatrix operator+(const SquareMatrix& B) const { return SquareMatrix(*this) += B; }
SquareMatrix operator-(const SquareMatrix& B) const { return SquareMatrix(*this) -= B; }
SquareMatrix operator*(const SquareMatrix& B) const { return SquareMatrix(*this) *= B; }
SquareMatrix operator*(const T& v) const { return SquareMatrix(*this) *= v; }
SquareMatrix operator/(const T& v) const { return SquareMatrix(*this) /= v; }
bool operator==(const SquareMatrix& B) const { return A == B.A; }
bool operator!=(const SquareMatrix& B) const { return A != B.A; }
SquareMatrix pow(long long n) const {
assert(0 <= n);
SquareMatrix x = *this, r = identity();
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
SquareMatrix transpose() const {
SquareMatrix res;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
res[j][i] = (*this)[i][j];
}
}
return res;
}
int rank() const { return SquareMatrix(*this).gauss_jordan().first; }
T det() const { return SquareMatrix(*this).gauss_jordan().second; }
SquareMatrix inv() const {
SquareMatrix B(*this), C = identity();
for (int j = 0; j < N; j++) {
int pivot = -1;
for (int i = j; i < N; i++) {
if (B[i][j] != T(0)) {
pivot = i;
break;
}
}
assert(pivot != -1);
if (pivot != j) {
std::swap(B[pivot], B[j]);
std::swap(C[pivot], C[j]);
}
{
T coef = T(1) / B[j][j];
for (int k = 0; k < N; k++) {
B[j][k] *= coef;
C[j][k] *= coef;
}
}
for (int i = 0; i < N; i++) {
if (i == j) continue;
T coef = B[i][j];
if (coef == T(0)) continue;
for (int k = 0; k < N; k++) {
B[i][k] -= B[j][k] * coef;
C[i][k] -= C[j][k] * coef;
}
}
}
return C;
}
friend std::ostream& operator<<(std::ostream& os, const SquareMatrix& p) {
os << "[(" << N << " * " << N << " Matrix)";
os << "\n[columun sums: ";
for (int j = 0; j < N; j++) {
T sum = 0;
for (int i = 0; i < N; i++) sum += p[i][j];
;
os << sum << (j + 1 < N ? "," : "");
}
os << "]";
for (int i = 0; i < N; i++) {
os << "\n[";
for (int j = 0; j < N; j++) os << p[i][j] << (j + 1 < N ? "," : "");
os << "]";
}
os << "]\n";
return os;
}
private:
std::pair<int, T> gauss_jordan() {
int rank = 0;
T det = 1;
for (int j = 0; j < N; j++) {
int pivot = -1;
for (int i = rank; i < N; i++) {
if ((*this)[i][j] != T(0)) {
pivot = i;
break;
}
}
if (pivot == -1) {
det = 0;
continue;
}
if (pivot != rank) {
det = -det;
std::swap((*this)[pivot], (*this)[rank]);
}
det *= A[rank][j];
if (A[rank][j] != T(1)) {
T coef = T(1) / (*this)[rank][j];
for (int k = j; k < N; k++) (*this)[rank][k] *= coef;
}
for (int i = 0; i < N; i++) {
if (i == rank) continue;
T coef = (*this)[i][j];
if (coef == T(0)) continue;
for (int k = j; k < N; k++) (*this)[i][k] -= (*this)[rank][k] * coef;
}
rank++;
}
return {rank, det};
}
};
using ll = long long;
using namespace std;
const int MAX = 6;
using mint = atcoder::modint998244353;
using SM = SquareMatrix<mint, MAX>;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
int N, M, K;
cin >> N >> M >> K;
SM m1, m2;
for (int i = 0; i + 1 < MAX; i++) m1[i + 1][i] = m2[i + 1][i] = 1;
for (int i = 0; i < MAX; i++) m1[i][MAX - 1] = 1;
mint tot = 0;
auto TOT = m1.pow(1LL * N * M - 1);
for (int i = 0; i < MAX; i++) tot += TOT[MAX - 1][i] * (i + 1);
auto query = [&](int C) -> mint {
SM m = SM::identity();
m *= m1.pow(C - 1);
m *= m2;
m *= (m1.pow(N - 1) * m2).pow(M - 1);
m *= m1.pow(N - 1 - C);
mint res = tot;
for (int i = 0; i < MAX; i++) res -= m[MAX - 1][i] * (i + 1);
return res;
};
for (; K--;) {
int C;
cin >> C;
cout << query(C).val() << "\n";
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0