結果
問題 | No.2807 Have Another Go (Easy) |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#include <bits/stdc++.h>#ifdef LOCAL#include <debug.hpp>#else#define debug(...) void(0)#endiftemplate <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;}