結果
| 問題 | No.2257 Swim and Sleep |
| ユーザー |
 noshi91
|
| 提出日時 | 2023-03-24 23:04:05 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,226 bytes |
| コンパイル時間 | 2,338 ms |
| コンパイル使用メモリ | 221,756 KB |
| 最終ジャッジ日時 | 2025-02-11 17:40:43 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 4 WA * 13 |
ソースコード
//#define NDEBUG#pragma warning(disable : 4146)#include <bits/stdc++.h>namespace n91 {using i32 = std::int32_t;using i64 = std::int64_t;using u32 = std::uint32_t;using u64 = std::uint64_t;using isize = std::ptrdiff_t;using usize = std::size_t;using f64 = double;struct rep {struct itr {usize i;constexpr itr(const usize i) noexcept : i(i) {}void operator++() noexcept { ++i; }constexpr usize operator*() const noexcept { return i; }constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }};const itr f, l;constexpr rep(const usize f, const usize l) noexcept: f(std::min(f, l)), l(l) {}constexpr auto begin() const noexcept { return f; }constexpr auto end() const noexcept { return l; }};struct revrep {struct itr {usize i;constexpr itr(const usize i) noexcept : i(i) {}void operator++() noexcept { --i; }constexpr usize operator*() const noexcept { return i; }constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }};const itr f, l;constexpr revrep(const usize f, const usize l) noexcept: f(l - 1), l(std::min(f, l) - 1) {}constexpr auto begin() const noexcept { return f; }constexpr auto end() const noexcept { return l; }};template <class T> auto md_vec(const usize n, const T& value) {return std::vector<T>(n, value);}template <class... Args> auto md_vec(const usize n, Args... args) {return std::vector<decltype(md_vec(args...))>(n, md_vec(args...));}template <class T> constexpr T difference(const T& a, const T& b) noexcept {return a < b ? b - a : a - b;}template <class T> void chmin(T& a, const T& b) noexcept {if (b < a)a = b;}template <class T> void chmax(T& a, const T& b) noexcept {if (a < b)a = b;}template <class F> class rec_lambda {F f;public:rec_lambda(F&& f_) : f(std::forward<F>(f_)) {}template <class... Args> auto operator()(Args &&... args) const {return f(*this, std::forward<Args>(args)...);}};template <class T> T scan() {T ret;std::cin >> ret;return ret;}constexpr char eoln = '\n';i64 floor_div(const i64 n, const i64 d) {assert(d != 0);return n / d - static_cast<i64>((n ^ d) < 0 && n % d != 0);}i64 ceil_div(const i64 n, const i64 d) {assert(d != 0);return n / d + static_cast<i64>((n ^ d) >= 0 && n % d != 0);}#ifdef N91_LOCAL#define OJ_LOCAL(a, b) b#else#define OJ_LOCAL(a, b) a#endif} // namespace n91#include <atcoder/modint>using mint = atcoder::modint998244353;namespace n91 {void solve() {const u32 a = scan<u32>();const u32 b = scan<u32>();const usize k = scan<usize>();struct w_t {u32 x, y;char d;};std::vector<w_t> ws(k);for (auto& [x, y, d] : ws) {std::cin >> x >> y >> d;}mint ans = 0;const u32 g = std::gcd(a, b);[&]() {std::map<u32, char> mp;for (const auto& [x, y, d] : ws) {if (d == 'U' || d == 'D')return;if (mp.count(y)) {if (mp[y] != d)return;}mp[y] = d;}ans += mint(2).pow(b - mp.size());}();[&]() {std::map<u32, char> mp;for (const auto& [x, y, d] : ws) {if (d == 'L' || d == 'R')return;if (mp.count(x)) {if (mp[x] != d)return;}mp[x] = d;}ans += mint(2).pow(a - mp.size());}();[&]() {std::map<u32, char> mp;for (const auto& [x, y, d] : ws) {if (d == 'L' || d == 'D')return;const u32 key = (x + y) % g;if (mp.count(key)) {if (mp[key] != d)return;}mp[key] = d;}ans += mint(2).pow(g - mp.size());}();[&]() {std::map<u32, char> mp;for (const auto& [x, y, d] : ws) {if (d == 'R' || d == 'U')return;const u32 key = (x + y) % g;if (mp.count(key)) {if (mp[key] != d)return;}mp[key] = d;}ans += mint(2).pow(g - mp.size());}();[&]() {std::map<u32, char> mp;for (const auto& [x, y, d] : ws) {if (d == 'L' || d == 'U')return;const u32 key = (x + b - y) % g;if (mp.count(key)) {if (mp[key] != d)return;}mp[key] = d;}ans += mint(2).pow(g - mp.size());}();[&]() {std::map<u32, char> mp;for (const auto& [x, y, d] : ws) {if (d == 'R' || d == 'D')return;const u32 key = (x + b - y) % g;if (mp.count(key)) {if (mp[key] != d)return;}mp[key] = d;}ans += mint(2).pow(g - mp.size());}();for (const char c : {'L', 'R', 'D', 'U'}) {bool ok = true;for (const auto& [x, y, d] : ws)if (d != c)ok = false;if (ok) {ans -= 2;}}if (g % 2 == 0) {[&]() {std::map<u32, char> mp0, mp1;for (const auto& [x, y, d] : ws) {if ((x + y) % 2 == 0) {if (d == 'U' || d == 'D')return;if (mp0.count(y) && mp0[y] != d)return;mp0[y] = d;}else {if (d == 'L' || d == 'R')return;if (mp1.count(x) && mp1[x] != d)return;mp1[x] = d;}}ans += mint(2).pow(b - mp0.size()) * mint(2).pow(a - mp1.size());std::set<char> st;for (const auto& [x, y, d] : ws)st.insert(d);for (const char x : {'U', 'D'}) {for (const char y : {'L', 'R'}) {if (!st.count(x) && !st.count(y))ans -= 1;}}}();[&]() {std::map<u32, char> mp0, mp1;for (const auto& [x, y, d] : ws) {if ((x + y) % 2 == 1) {if (d == 'U' || d == 'D')return;if (mp0.count(y) && mp0[y] != d)return;mp0[y] = d;}else {if (d == 'L' || d == 'R')return;if (mp1.count(x) && mp1[x] != d)return;mp1[x] = d;}}ans += mint(2).pow(b - mp0.size()) * mint(2).pow(a - mp1.size());std::set<char> st;for (const auto& [x, y, d] : ws)st.insert(d);for (const char x : {'U', 'D'}) {for (const char y : {'L', 'R'}) {if (!st.count(x) && !st.count(y))ans -= 1;}}}();}std::cout << ans.val() << eoln;}void main_() {const usize t = scan<usize>();for (const usize i : rep(0, t))solve();}} // namespace n91int main() {//*std::ios::sync_with_stdio(false);std::cin.tie(nullptr);//*/std::cout << std::fixed << std::setprecision(20);n91::main_();return 0;}