結果
問題 | No.1241 Eternal Tours |
ユーザー |
![]() |
提出日時 | 2020-10-06 11:51:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 44 ms / 6,000 ms |
コード長 | 1,968 bytes |
コンパイル時間 | 689 ms |
コンパイル使用メモリ | 74,016 KB |
最終ジャッジ日時 | 2025-01-15 02:59:48 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <iostream> #include <vector> #include <cassert> using u32 = unsigned; using u64 = unsigned long long; template <u32 MOD> struct Mint { u32 n; constexpr Mint(u32 n = 0): n(n) {} constexpr Mint &operator+=(const Mint &rhs){ n += rhs.n; if(n >= MOD) n -= MOD; return *this; } constexpr Mint &operator-=(const Mint &rhs){ if(rhs.n > n) n += MOD; n -= rhs.n; return *this; } constexpr Mint &operator*=(const Mint &rhs){ n = (u64) n * rhs.n % MOD; return *this; } friend constexpr Mint operator+(const Mint &lhs, const Mint &rhs){ return Mint(lhs) += rhs; } friend constexpr Mint operator-(const Mint &lhs, const Mint &rhs){ return Mint(lhs) -= rhs; } friend constexpr Mint operator*(const Mint &lhs, const Mint &rhs){ return Mint(lhs) *= rhs; } }; template <class T> T pow(T a, u64 n){ T r = 1; for(; n; n >>= 1){ if(n&1) r *= a; a *= a; } return r; } constexpr u32 mod = 998244353; using mint = Mint<mod>; constexpr mint root = 3; u64 x, y, t, a, b, c, d; int main(){ std::cin >> x >> y >> t >> a >> b >> c >> d; if(x < y){ std::swap(x, y); std::swap(a, b); std::swap(c, d); } std::vector<mint> wx((1 << (x+1)) + 1); const mint rootx = pow(root, (mod-1)/(1 << (x+1))); wx[0] = 1; for(int i = 1; i <= (1 << (x+1)); ++i) wx[i] = wx[i-1] * rootx; t %= mod - 1; const u32 mask = (1 << (x+1)) - 1; mint ans = 0; for(u32 i = 0; i < (1U << x); ++i){ for(u32 j = 0; j < (1U << y); ++j){ u32 ai = a * i; u32 bj = (b * j) << (x-y); u32 ci = c * i; u32 dj = (d * j) << (x-y); u32 jj = j << (x-y); ans += (wx[ai & mask] - wx[-ai & mask]) * (wx[bj & mask] - wx[-bj & mask]) * (wx[ci & mask] - wx[-ci & mask]) * (wx[dj & mask] - wx[-dj & mask]) * pow(wx[i] + wx[-i & mask] + wx[jj] + wx[-jj & mask] + 1, t); } } for(u32 i = 0; i < x + y + 2; ++i){ if(ans.n & 1) ans.n += mod; ans.n /= 2; } std::cout << ans.n << std::endl; return 0; }