結果
| 問題 |
No.3255 01 Matrix Counting
|
| コンテスト | |
| ユーザー |
 nono00
|
| 提出日時 | 2025-09-05 22:52:14 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 13,257 bytes |
| コンパイル時間 | 3,419 ms |
| コンパイル使用メモリ | 278,332 KB |
| 実行使用メモリ | 7,716 KB |
| 最終ジャッジ日時 | 2025-09-05 22:52:26 |
| 合計ジャッジ時間 | 4,174 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 14 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
template <class T>
using MaxHeap = std::priority_queue<T>;
template <class T>
using MinHeap = std::priority_queue<T, vector<T>, greater<T>>;
#define rep2(i, n) for (ll i = 0; i < (n); i++)
#define rep3(i, l, r) for (ll i = (l); i < (r); i++)
#define rrep2(i, n) for (ll i = n; i-- > 0;)
#define rrep3(i, r, l) for (ll i = (r); i-- > (l);)
#define overload(a, b, c, d, ...) d
#define rep(...) overload(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define rrep(...) overload(__VA_ARGS__, rrep3, rrep2)(__VA_ARGS__)
#define all(x) begin(x), end(x)
bool chmin(auto& lhs, auto rhs) {
return lhs > rhs ? lhs = rhs, 1 : 0;
}
bool chmax(auto& lhs, auto rhs) {
return lhs < rhs ? lhs = rhs, 1 : 0;
}
struct IOIO {
IOIO() {
std::cin.tie(0)->sync_with_stdio(0);
}
} ioio;
#include <iostream>
#include <type_traits>
#include <utility>
/// brief : aclベースのmodint. cin, coutによる入出力に対応.
namespace nono {
namespace internal {
namespace modint {
// @param m `1 <= m`
// @return x mod m
constexpr long long safe_mod(long long x, long long m) {
x %= m;
if (x < 0) x += m;
return x;
}
// Fast modular multiplication by barrett reduction
// Reference: https://en.wikipedia.org/wiki/Barrett_reduction
// NOTE: reconsider after Ice Lake
struct barrett {
unsigned int _m;
unsigned long long im;
// @param m `1 <= m`
explicit barrett(unsigned int m): _m(m), im((unsigned long long)(-1) / m + 1) {}
// @return m
unsigned int umod() const {
return _m;
}
// @param a `0 <= a < m`
// @param b `0 <= b < m`
// @return `a * b % m`
unsigned int mul(unsigned int a, unsigned int b) const {
// [1] m = 1
// a = b = im = 0, so okay
// [2] m >= 2
// im = ceil(2^64 / m)
// -> im * m = 2^64 + r (0 <= r < m)
// let z = a*b = c*m + d (0 <= c, d < m)
// a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im
// c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2
// ((ab * im) >> 64) == c or c + 1
unsigned long long z = a;
z *= b;
unsigned long long x = (unsigned long long)(((unsigned __int128)(z)*im) >> 64);
unsigned long long y = x * _m;
return (unsigned int)(z - y + (z < y ? _m : 0));
}
};
// @param n `0 <= n`
// @param m `1 <= m`
// @return `(x ** n) % m`
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
if (m == 1) return 0;
unsigned int _m = (unsigned int)(m);
unsigned long long r = 1;
unsigned long long y = safe_mod(x, m);
while (n) {
if (n & 1) r = (r * y) % _m;
y = (y * y) % _m;
n >>= 1;
}
return r;
}
// Reference:
// M. Forisek and J. Jancina,
// Fast Primality Testing for Integers That Fit into a Machine Word
// @param n `0 <= n`
constexpr bool is_prime_constexpr(int n) {
if (n <= 1) return false;
if (n == 2 || n == 7 || n == 61) return true;
if (n % 2 == 0) return false;
long long d = n - 1;
while (d % 2 == 0) d /= 2;
constexpr long long bases[3] = {2, 7, 61};
for (long long a: bases) {
long long t = d;
long long y = pow_mod_constexpr(a, t, n);
while (t != n - 1 && y != 1 && y != n - 1) {
y = y * y % n;
t <<= 1;
}
if (y != n - 1 && t % 2 == 0) {
return false;
}
}
return true;
}
template <int n>
constexpr bool is_prime = is_prime_constexpr(n);
// @param b `1 <= b`
// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
a = safe_mod(a, b);
if (a == 0) return {b, 0};
// Contracts:
// [1] s - m0 * a = 0 (mod b)
// [2] t - m1 * a = 0 (mod b)
// [3] s * |m1| + t * |m0| <= b
long long s = b, t = a;
long long m0 = 0, m1 = 1;
while (t) {
long long u = s / t;
s -= t * u;
m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b
// [3]:
// (s - t * u) * |m1| + t * |m0 - m1 * u|
// <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
// = s * |m1| + t * |m0| <= b
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
// by [3]: |m0| <= b/g
// by g != b: |m0| < b/g
if (m0 < 0) m0 += b / s;
return {s, m0};
}
template <class T>
using is_signed_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value || std::is_same<T, __int128>::value, std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value || std::is_same<T, unsigned __int128>::value,
std::true_type, std::false_type>::type;
template <class T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value, __uint128_t, unsigned __int128>;
template <class T>
using is_integral =
typename std::conditional<std::is_integral<T>::value || is_signed_int128<T>::value || is_unsigned_int128<T>::value,
std::true_type, std::false_type>::type;
template <class T>
using is_signed_int =
typename std::conditional<(is_integral<T>::value && std::is_signed<T>::value) || is_signed_int128<T>::value,
std::true_type, std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<(is_integral<T>::value && std::is_unsigned<T>::value) || is_unsigned_int128<T>::value,
std::true_type, std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<
is_signed_int128<T>::value, make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value, std::make_unsigned<T>, std::common_type<T>>::type>::type;
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template <class T>
using to_unsigned_t = typename to_unsigned<T>::type;
} // namespace modint
} // namespace internal
} // namespace nono
namespace nono {
template <int m, std::enable_if_t<(1 <= m)>* = nullptr>
struct StaticModint {
using Mint = StaticModint;
public:
static constexpr int mod() {
return m;
}
static Mint raw(int v) {
Mint x;
x._v = v;
return x;
}
StaticModint(): _v(0) {}
template <class T, internal::modint::is_signed_int_t<T>* = nullptr>
StaticModint(T v) {
long long x = (long long)(v % (long long)(umod()));
if (x < 0) x += umod();
_v = (unsigned int)(x);
}
template <class T, internal::modint::is_unsigned_int_t<T>* = nullptr>
StaticModint(T v) {
_v = (unsigned int)(v % umod());
}
unsigned int val() const {
return _v;
}
Mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
Mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
Mint operator++(int) {
Mint result = *this;
++*this;
return result;
}
Mint operator--(int) {
Mint result = *this;
--*this;
return result;
}
Mint& operator+=(const Mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
Mint& operator-=(const Mint& rhs) {
_v -= rhs._v;
if (_v >= umod()) _v += umod();
return *this;
}
Mint& operator*=(const Mint& rhs) {
unsigned long long z = _v;
z *= rhs._v;
_v = (unsigned int)(z % umod());
return *this;
}
Mint& operator/=(const Mint& rhs) {
return *this = *this * rhs.inv();
}
Mint operator+() const {
return *this;
}
Mint operator-() const {
return Mint() - *this;
}
Mint pow(long long n) const {
Mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
Mint inv() const {
if (prime) {
return pow(umod() - 2);
} else {
auto eg = internal::modint::inv_gcd(_v, m);
return eg.second;
}
}
friend Mint operator+(const Mint& lhs, const Mint& rhs) {
return Mint(lhs) += rhs;
}
friend Mint operator-(const Mint& lhs, const Mint& rhs) {
return Mint(lhs) -= rhs;
}
friend Mint operator*(const Mint& lhs, const Mint& rhs) {
return Mint(lhs) *= rhs;
}
friend Mint operator/(const Mint& lhs, const Mint& rhs) {
return Mint(lhs) /= rhs;
}
friend bool operator==(const Mint& lhs, const Mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const Mint& lhs, const Mint& rhs) {
return lhs._v != rhs._v;
}
friend std::istream& operator>>(std::istream& is, Mint& v) {
long long x;
is >> x;
v = Mint(x);
return is;
}
friend std::ostream& operator<<(std::ostream& os, const Mint& v) {
return os << v.val();
}
private:
unsigned int _v;
static constexpr unsigned int umod() {
return m;
}
static constexpr bool prime = internal::modint::is_prime<m>;
};
template <int id>
struct DynamicModint {
using Mint = DynamicModint;
public:
static int mod() {
return (int)(bt.umod());
}
static void set_mod(int m) {
bt = internal::modint::barrett(m);
}
static Mint raw(int v) {
Mint x;
x._v = v;
return x;
}
DynamicModint(): _v(0) {}
template <class T, internal::modint::is_signed_int_t<T>* = nullptr>
DynamicModint(T v) {
long long x = (long long)(v % (long long)(mod()));
if (x < 0) x += mod();
_v = (unsigned int)(x);
}
template <class T, internal::modint::is_unsigned_int_t<T>* = nullptr>
DynamicModint(T v) {
_v = (unsigned int)(v % mod());
}
unsigned int val() const {
return _v;
}
Mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
Mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
Mint operator++(int) {
Mint result = *this;
++*this;
return result;
}
Mint operator--(int) {
Mint result = *this;
--*this;
return result;
}
Mint& operator+=(const Mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
Mint& operator-=(const Mint& rhs) {
_v += mod() - rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
Mint& operator*=(const Mint& rhs) {
_v = bt.mul(_v, rhs._v);
return *this;
}
Mint& operator/=(const Mint& rhs) {
return *this = *this * rhs.inv();
}
Mint operator+() const {
return *this;
}
Mint operator-() const {
return Mint() - *this;
}
Mint pow(long long n) const {
Mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
Mint inv() const {
auto eg = internal::modint::inv_gcd(_v, mod());
return eg.second;
}
friend Mint operator+(const Mint& lhs, const Mint& rhs) {
return Mint(lhs) += rhs;
}
friend Mint operator-(const Mint& lhs, const Mint& rhs) {
return Mint(lhs) -= rhs;
}
friend Mint operator*(const Mint& lhs, const Mint& rhs) {
return Mint(lhs) *= rhs;
}
friend Mint operator/(const Mint& lhs, const Mint& rhs) {
return Mint(lhs) /= rhs;
}
friend bool operator==(const Mint& lhs, const Mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const Mint& lhs, const Mint& rhs) {
return lhs._v != rhs._v;
}
friend std::istream& operator<<(std::istream& is, Mint& v) {
long long x;
is >> x;
v = Mint(x);
return is;
}
friend std::ostream& operator<<(std::ostream& os, const Mint& v) {
return os << v.val();
}
private:
unsigned int _v;
static internal::modint::barrett bt;
static unsigned int umod() {
return bt.umod();
}
};
template <int id>
internal::modint::barrett DynamicModint<id>::bt(998244353);
using Modint998244353 = StaticModint<998244353>;
using Modint1000000007 = StaticModint<1000000007>;
using Modint = DynamicModint<-1>;
} // namespace nono
// ? ? x x
// ? ? 1 x
// x 0 1 x
// x x x x
void solve() {
using Mint = nono::Modint998244353;
ll h, w;
cin >> h >> w;
Mint ans = 8 * Mint(2).pow((h - 2) * (w - 2) + (h - 2) + (w - 2));
cout << ans << endl;
}
int main() {
int t = 1;
// cin >> t;
while (t--) solve();
}