結果
問題 | No.1241 Eternal Tours |
ユーザー |
![]() |
提出日時 | 2020-09-25 21:53:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 547 ms / 6,000 ms |
コード長 | 15,007 bytes |
コンパイル時間 | 1,519 ms |
コンパイル使用メモリ | 129,564 KB |
最終ジャッジ日時 | 2025-01-14 20:53:49 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
//#pragma GCC optimize("Ofast")//#pragma GCC target("avx")//#undef LOCAL#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <complex>#include <cstdio>#include <cstring>#include <iostream>#include <map>#include <numeric>#include <queue>#include <set>#include <string>#include <unordered_map>#include <unordered_set>#include <vector>using namespace std;using uint = unsigned int;using ll = long long;using ull = unsigned long long;constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }template <class T> using V = vector<T>;template <class T> using VV = V<V<T>>;#include <unistd.h>struct Scanner {int fd = -1;char line[(1 << 15) + 1];size_t st = 0, ed = 0;void reread() {memmove(line, line + st, ed - st);ed -= st;st = 0;ed += ::read(fd, line + ed, (1 << 15) - ed);line[ed] = '\0';}bool succ() {while (true) {if (st == ed) {reread();if (st == ed) return false;}while (st != ed && isspace(line[st])) st++;if (st != ed) break;}if (ed - st <= 50) {bool sep = false;for (size_t i = st; i < ed; i++) {if (isspace(line[i])) {sep = true;break;}}if (!sep) reread();}return true;}template <class T, enable_if_t<is_same<T, string>::value, int> = 0>bool read_single(T& ref) {if (!succ()) return false;while (true) {size_t sz = 0;while (st + sz < ed && !isspace(line[st + sz])) sz++;ref.append(line + st, sz);st += sz;if (!sz || st != ed) break;reread();}return true;}template <class T, enable_if_t<is_integral<T>::value>* = nullptr>bool read_single(T& ref) {if (!succ()) return false;bool neg = false;if (line[st] == '-') {neg = true;st++;}ref = T(0);while (isdigit(line[st])) {ref = 10 * ref + (line[st++] & 0xf);}if (neg) ref = -ref;return true;}template <class T> bool read_single(V<T>& ref) {for (auto& d : ref) {if (!read_single(d)) return false;}return true;}void read() {}template <class H, class... T> void read(H& h, T&... t) {bool f = read_single(h);assert(f);read(t...);}int read_unsafe() { return 0; }template <class H, class... T> int read_unsafe(H& h, T&... t) {bool f = read_single(h);if (!f) return 0;return 1 + read_unsafe(t...);}Scanner(FILE* fp) : fd(fileno(fp)) {}};struct Printer {public:template <bool F = false> void write() {}template <bool F = false, class H, class... T>void write(const H& h, const T&... t) {if (F) write_single(' ');write_single(h);write<true>(t...);}template <class... T> void writeln(const T&... t) {write(t...);write_single('\n');}Printer(FILE* _fp) : fp(_fp) {}~Printer() { flush(); }private:static constexpr size_t SIZE = 1 << 15;FILE* fp;char line[SIZE], small[50];size_t pos = 0;void flush() {fwrite(line, 1, pos, fp);pos = 0;}void write_single(const char& val) {if (pos == SIZE) flush();line[pos++] = val;}template <class T, enable_if_t<is_integral<T>::value>* = nullptr>void write_single(T val) {if (pos > (1 << 15) - 50) flush();if (val == 0) {write_single('0');return;}if (val < 0) {write_single('-');val = -val; // todo min}size_t len = 0;while (val) {small[len++] = char(0x30 | (val % 10));val /= 10;}for (size_t i = 0; i < len; i++) {line[pos + i] = small[len - 1 - i];}pos += len;}void write_single(__int128 val) {if (pos > (1 << 15) - 50) flush();if (val == 0) {write_single('0');return;}if (val < 0) {write_single('-');val = -val; // todo min}size_t len = 0;while (val) {small[len++] = char(0x30 | (val % 10));val /= 10;}for (size_t i = 0; i < len; i++) {line[pos + i] = small[len - 1 - i];}pos += len;}void write_single(const string& s) {for (char c : s) write_single(c);}void write_single(const char* s) {size_t len = strlen(s);for (size_t i = 0; i < len; i++) write_single(s[i]);}template <class T> void write_single(const V<T>& val) {auto n = val.size();for (size_t i = 0; i < n; i++) {if (i) write_single(' ');write_single(val[i]);}}};template <uint MD> struct ModInt {using M = ModInt;static constexpr uint get_mod() { return MD; }const static M G;uint v;ModInt(ll _v = 0) { set_v(uint(_v % MD + MD)); }M& set_v(uint _v) {v = (_v < MD) ? _v : _v - MD;return *this;}explicit operator bool() const { return v != 0; }M operator-() const { return M() - *this; }M operator+(const M& r) const { return M().set_v(v + r.v); }M operator-(const M& r) const { return M().set_v(v + MD - r.v); }M operator*(const M& r) const { return M().set_v(uint(ull(v) * r.v % MD)); }M operator/(const M& r) const { return *this * r.inv(); }M& operator+=(const M& r) { return *this = *this + r; }M& operator-=(const M& r) { return *this = *this - r; }M& operator*=(const M& r) { return *this = *this * r; }M& operator/=(const M& r) { return *this = *this / r; }bool operator==(const M& r) const { return v == r.v; }M pow(ll n) const {M x = *this, r = 1;while (n) {if (n & 1) r *= x;x *= x;n >>= 1;}return r;}M inv() const { return pow(MD - 2); }friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }};// using Mint = ModInt<998244353>;// template<> const Mint Mint::G = Mint(3);// bit opint popcnt(uint x) { return __builtin_popcount(x); }int popcnt(ull x) { return __builtin_popcountll(x); }int bsr(uint x) { return 31 - __builtin_clz(x); }int bsr(ull x) { return 63 - __builtin_clzll(x); }int bsf(uint x) { return __builtin_ctz(x); }int bsf(ull x) { return __builtin_ctzll(x); }//binary gcdll gcd(ll _a, ll _b) {ull a = abs(_a), b = abs(_b);if (a == 0) return b;if (b == 0) return a;int shift = bsf(a|b);a >>= bsf(a);do {b >>= bsf(b);if (a > b) swap(a, b);b -= a;} while (b);return (a << shift);}/// g:gcd(a, b), ax+by=gstruct EG { ll g, x, y; };EG ext_gcd(ll a, ll b) {if (b == 0) {if (a >= 0) return EG{a, 1, 0};else return EG{-a, -1, 0};} else {auto e = ext_gcd(b, a % b);return EG{e.g, e.y, e.x - a / b * e.y};}}ll inv_mod(ll x, ll md) {auto z = ext_gcd(x, md).x;return (z % md + md) % md;}template<class T, class U>T pow_mod(T x, U n, T md) {T r = 1 % md;x %= md;while (n) {if (n & 1) r = (r * x) % md;x = (x * x) % md;n >>= 1;}return r;}// (rem, mod)pair<ll, ll> crt(const V<ll>& b, const V<ll>& c) {int n = int(b.size());ll r = 0, m = 1;for (int i = 0; i < n; i++) {auto eg = ext_gcd(m, c[i]);ll g = eg.g, im = eg.x;if ((b[i] - r) % g) return {0, -1};ll tmp = (b[i] - r) / g * im % (c[i] / g);r += m * tmp;m *= c[i] / g;}return {(r % m + m) % m, m};}template <class Mint> void nft(bool type, V<Mint>& a) {int n = int(a.size()), s = 0;while ((1 << s) < n) s++;assert(1 << s == n);static V<Mint> ep, iep;while (int(ep.size()) <= s) {ep.push_back(Mint::G.pow(Mint(-1).v / (1 << ep.size())));iep.push_back(ep.back().inv());}V<Mint> b(n);for (int i = 1; i <= s; i++) {int w = 1 << (s - i);Mint base = type ? iep[i] : ep[i], now = 1;for (int y = 0; y < n / 2; y += w) {for (int x = 0; x < w; x++) {auto l = a[y << 1 | x];auto r = now * a[y << 1 | x | w];b[y | x] = l + r;b[y | x | n >> 1] = l - r;}now *= base;}swap(a, b);}}template <class Mint> V<Mint> multiply_nft(const V<Mint>& a, const V<Mint>& b) {int n = int(a.size()), m = int(b.size());if (!n || !m) return {};if (min(n, m) <= 8) {V<Mint> ans(n + m - 1);for (int i = 0; i < n; i++)for (int j = 0; j < m; j++) ans[i + j] += a[i] * b[j];return ans;}int lg = 0;while ((1 << lg) < n + m - 1) lg++;int z = 1 << lg;auto a2 = a, b2 = b;a2.resize(z);b2.resize(z);nft(false, a2);nft(false, b2);for (int i = 0; i < z; i++) a2[i] *= b2[i];nft(true, a2);a2.resize(n + m - 1);Mint iz = Mint(z).inv();for (int i = 0; i < n + m - 1; i++) a2[i] *= iz;return a2;}// Cooley-Tukey: input -> butterfly -> bit reversing -> output から// bit reversingを抜いたもの 直接使うなtemplate <class Mint> void butterfly(bool type, V<Mint>& a) {int n = int(a.size()), h = 0;while ((1 << h) < n) h++;assert(1 << h == n);if (n == 1) return;static V<Mint> snow, sinow;if (snow.empty()) {Mint sep = Mint(1), siep = Mint(1);uint mod = Mint(-1).v;uint di = 4;while (mod % di == 0) {Mint ep = Mint::G.pow(mod / di);Mint iep = ep.inv();snow.push_back(siep * ep);sinow.push_back(sep * iep);sep *= ep;siep *= iep;di *= 2;}}if (!type) {// fftfor (int ph = 1; ph <= h; ph++) {// phase ph: size w -> 2w の FFT, p 並列int w = 1 << (ph - 1), p = 1 << (h - ph);Mint now = Mint(1);for (int s = 0; s < w; s++) {int offset = s << (h - ph + 1);for (int i = 0; i < p; i++) {auto l = a[i + offset];auto r = a[i + offset + p] * now;a[i + offset] = l + r;a[i + offset + p] = l - r;}int u = bsf(~uint(s));now *= snow[u];}}} else {// ifftfor (int ph = h; ph >= 1; ph--) {int w = 1 << (ph - 1), p = 1 << (h - ph);Mint inow = Mint(1);for (int s = 0; s < w; s++) {int offset = s << (h - ph + 1);for (int i = 0; i < p; i++) {auto l = a[i + offset];auto r = a[i + offset + p];a[i + offset] = l + r;a[i + offset + p] = (l - r) * inow;}int u = bsf(~uint(s));inow *= sinow[u];}}}}template <class Mint> V<Mint> multiply(const V<Mint>& a, const V<Mint>& b) {int n = int(a.size()), m = int(b.size());if (!n || !m) return {};if (min(n, m) < 8) {V<Mint> ans(n + m - 1);for (int i = 0; i < n; i++)for (int j = 0; j < m; j++) ans[i + j] += a[i] * b[j];return ans;}int lg = 0;while ((1 << lg) < n + m - 1) lg++;int z = 1 << lg;auto a2 = a;a2.resize(z);butterfly(false, a2);if (a == b) {for (int i = 0; i < z; i++) a2[i] *= a2[i];} else {auto b2 = b;b2.resize(z);butterfly(false, b2);for (int i = 0; i < z; i++) a2[i] *= b2[i];}butterfly(true, a2);a2.resize(n + m - 1);Mint iz = Mint(z).inv();for (int i = 0; i < n + m - 1; i++) a2[i] *= iz;return a2;}using mint = ModInt<998244353>;template<> const mint mint::G = mint(3);Scanner sc = Scanner(stdin);Printer pr = Printer(stdout);int main() {int x, y; ll t; int a, b, c, d;sc.read(x, y, t, a, b, c, d);a--; b--; c--; d--;bool sig = t % 2;t -= t % 2;auto but2 = [&](bool type, VV<mint>& a) {int h = int(a.size());int w = int(a[0].size());for (auto& x : a) {butterfly(type, x);}V<mint> buf(h);for (int i = 0; i < w; i++) {for (int j = 0; j < h; j++) {buf[j] = a[j][i];}butterfly(type, buf);for (int j = 0; j < h; j++) {a[j][i] = buf[j];}}};auto mul = [&](VV<mint> a, VV<mint> b) {int h = int(a.size());int w = int(a[0].size());but2(false, a);but2(false, b);for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {a[i][j] *= b[i][j];}}but2(true, a);mint in = (mint(h) * w).inv();for (auto& v: a) for (auto& x: v) x *= in;return a;};int h = 2 << x;int w = 2 << y;VV<mint> f(h, V<mint>(w));{f[0][0] += mint(1);f[0][1] += mint(1);f[1][0] += mint(1);f[0][w-1] += mint(1);f[h-1][0] += mint(1);but2(false, f);for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {f[i][j] = f[i][j].pow(t);}}but2(true, f);mint in = (mint(h) * w).inv();for (auto& v: f) for (auto& z: v) z *= in;VV<mint> g(h, V<mint>(w));g[a][b] = 1;f = mul(f, g);/* auto t2 = t;while (t2) {if (t2 & 1) {g = mul(f, g);}f = mul(f, f);t2 >>= 1;}f = g;*/}auto solve = [&](int tx, int ty) {mint ans = 0;ans += f[tx][ty];ans -= f[h - 2 - tx][ty];ans -= f[tx][w - 2 - ty];ans += f[h - 2 - tx][w - 2 - ty];;return ans;};mint ans = solve(c, d);if (sig) {ans = solve(c, d);if (c) ans += solve(c - 1, d);if (d) ans += solve(c, d - 1);if (c + 1 < ((1 << x) - 1)) ans += solve(c + 1, d);if (d + 1 < ((1 << y) - 1)) ans += solve(c, d + 1);}pr.writeln(ans.v);return 0;}