結果
| 問題 | No.2983 Christmas Color Grid (Advent Calender ver.) |
| ユーザー |
 tko919
|
| 提出日時 | 2024-12-08 03:45:09 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 3,340 ms |
| コード長 | 20,476 bytes |
| コンパイル時間 | 5,450 ms |
| コンパイル使用メモリ | 318,616 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-12-08 03:45:17 |
| 合計ジャッジ時間 | 7,321 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 64 |
ソースコード
#line 1 "library/Template/template.hpp"#include <bits/stdc++.h>using namespace std;#define rep(i, a, b) for (int i = (int)(a); i < (int)(b); i++)#define rrep(i, a, b) for (int i = (int)(b)-1; i >= (int)(a); i--)#define ALL(v) (v).begin(), (v).end()#define UNIQUE(v) sort(ALL(v)), (v).erase(unique(ALL(v)), (v).end())#define SZ(v) (int)v.size()#define MIN(v) *min_element(ALL(v))#define MAX(v) *max_element(ALL(v))#define LB(v, x) int(lower_bound(ALL(v), (x)) - (v).begin())#define UB(v, x) int(upper_bound(ALL(v), (x)) - (v).begin())using uint = unsigned int;using ll = long long int;using ull = unsigned long long;using i128 = __int128_t;using u128 = __uint128_t;const int inf = 0x3fffffff;const ll INF = 0x1fffffffffffffff;template <typename T> inline bool chmax(T &a, T b) {if (a < b) {a = b;return 1;}return 0;}template <typename T> inline bool chmin(T &a, T b) {if (a > b) {a = b;return 1;}return 0;}template <typename T, typename U> T ceil(T x, U y) {assert(y != 0);if (y < 0)x = -x, y = -y;return (x > 0 ? (x + y - 1) / y : x / y);}template <typename T, typename U> T floor(T x, U y) {assert(y != 0);if (y < 0)x = -x, y = -y;return (x > 0 ? x / y : (x - y + 1) / y);}template <typename T> int popcnt(T x) {return __builtin_popcountll(x);}template <typename T> int topbit(T x) {return (x == 0 ? -1 : 63 - __builtin_clzll(x));}template <typename T> int lowbit(T x) {return (x == 0 ? -1 : __builtin_ctzll(x));}template <class T, class U>ostream &operator<<(ostream &os, const pair<T, U> &p) {os << "P(" << p.first << ", " << p.second << ")";return os;}template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) {os << "{";for (int i = 0; i < vec.size(); i++) {os << vec[i] << (i + 1 == vec.size() ? "" : ", ");}os << "}";return os;}template <typename T, typename U>ostream &operator<<(ostream &os, const map<T, U> &map_var) {os << "{";for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {os << "(" << itr->first << ", " << itr->second << ")";itr++;if (itr != map_var.end())os << ", ";itr--;}os << "}";return os;}template <typename T> ostream &operator<<(ostream &os, const set<T> &set_var) {os << "{";for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {os << *itr;++itr;if (itr != set_var.end())os << ", ";itr--;}os << "}";return os;}#ifdef LOCAL#define show(...) _show(0, #__VA_ARGS__, __VA_ARGS__)#else#define show(...) true#endiftemplate <typename T> void _show(int i, T name) {cerr << '\n';}template <typename T1, typename T2, typename... T3>void _show(int i, const T1 &a, const T2 &b, const T3 &...c) {for (; a[i] != ',' && a[i] != '\0'; i++)cerr << a[i];cerr << ":" << b << " ";_show(i + 1, a, c...);}#line 2 "library/Utility/fastio.hpp"#include <unistd.h>namespace fastio {static constexpr uint32_t SZ = 1 << 17;char ibuf[SZ];char obuf[SZ];char out[100];// pointer of ibuf, obufuint32_t pil = 0, pir = 0, por = 0;struct Pre {char num[10000][4];constexpr Pre() : num() {for (int i = 0; i < 10000; i++) {int n = i;for (int j = 3; j >= 0; j--) {num[i][j] = n % 10 | '0';n /= 10;}}}} constexpr pre;inline void load() {memmove(ibuf, ibuf + pil, pir - pil);pir = pir - pil + fread(ibuf + pir - pil, 1, SZ - pir + pil, stdin);pil = 0;if (pir < SZ)ibuf[pir++] = '\n';}inline void flush() {fwrite(obuf, 1, por, stdout);por = 0;}void rd(char &c) {do {if (pil + 1 > pir)load();c = ibuf[pil++];} while (isspace(c));}void rd(string &x) {x.clear();char c;do {if (pil + 1 > pir)load();c = ibuf[pil++];} while (isspace(c));do {x += c;if (pil == pir)load();c = ibuf[pil++];} while (!isspace(c));}template <typename T> void rd_real(T &x) {string s;rd(s);x = stod(s);}template <typename T> void rd_integer(T &x) {if (pil + 100 > pir)load();char c;doc = ibuf[pil++];while (c < '-');bool minus = 0;if constexpr (is_signed<T>::value || is_same_v<T, i128>) {if (c == '-') {minus = 1, c = ibuf[pil++];}}x = 0;while ('0' <= c) {x = x * 10 + (c & 15), c = ibuf[pil++];}if constexpr (is_signed<T>::value || is_same_v<T, i128>) {if (minus)x = -x;}}void rd(int &x) {rd_integer(x);}void rd(ll &x) {rd_integer(x);}void rd(i128 &x) {rd_integer(x);}void rd(uint &x) {rd_integer(x);}void rd(ull &x) {rd_integer(x);}void rd(u128 &x) {rd_integer(x);}void rd(double &x) {rd_real(x);}void rd(long double &x) {rd_real(x);}template <class T, class U> void rd(pair<T, U> &p) {return rd(p.first), rd(p.second);}template <size_t N = 0, typename T> void rd_tuple(T &t) {if constexpr (N < std::tuple_size<T>::value) {auto &x = std::get<N>(t);rd(x);rd_tuple<N + 1>(t);}}template <class... T> void rd(tuple<T...> &tpl) {rd_tuple(tpl);}template <size_t N = 0, typename T> void rd(array<T, N> &x) {for (auto &d : x)rd(d);}template <class T> void rd(vector<T> &x) {for (auto &d : x)rd(d);}void read() {}template <class H, class... T> void read(H &h, T &...t) {rd(h), read(t...);}void wt(const char c) {if (por == SZ)flush();obuf[por++] = c;}void wt(const string s) {for (char c : s)wt(c);}void wt(const char *s) {size_t len = strlen(s);for (size_t i = 0; i < len; i++)wt(s[i]);}template <typename T> void wt_integer(T x) {if (por > SZ - 100)flush();if (x < 0) {obuf[por++] = '-', x = -x;}int outi;for (outi = 96; x >= 10000; outi -= 4) {memcpy(out + outi, pre.num[x % 10000], 4);x /= 10000;}if (x >= 1000) {memcpy(obuf + por, pre.num[x], 4);por += 4;} else if (x >= 100) {memcpy(obuf + por, pre.num[x] + 1, 3);por += 3;} else if (x >= 10) {int q = (x * 103) >> 10;obuf[por] = q | '0';obuf[por + 1] = (x - q * 10) | '0';por += 2;} elseobuf[por++] = x | '0';memcpy(obuf + por, out + outi + 4, 96 - outi);por += 96 - outi;}template <typename T> void wt_real(T x) {ostringstream oss;oss << fixed << setprecision(15) << double(x);string s = oss.str();wt(s);}void wt(int x) {wt_integer(x);}void wt(ll x) {wt_integer(x);}void wt(i128 x) {wt_integer(x);}void wt(uint x) {wt_integer(x);}void wt(ull x) {wt_integer(x);}void wt(u128 x) {wt_integer(x);}void wt(double x) {wt_real(x);}void wt(long double x) {wt_real(x);}template <class T, class U> void wt(const pair<T, U> val) {wt(val.first);wt(' ');wt(val.second);}template <size_t N = 0, typename T> void wt_tuple(const T t) {if constexpr (N < std::tuple_size<T>::value) {if constexpr (N > 0) {wt(' ');}const auto x = std::get<N>(t);wt(x);wt_tuple<N + 1>(t);}}template <class... T> void wt(tuple<T...> tpl) {wt_tuple(tpl);}template <class T, size_t S> void wt(const array<T, S> val) {auto n = val.size();for (size_t i = 0; i < n; i++) {if (i)wt(' ');wt(val[i]);}}template <class T> void wt(const vector<T> val) {auto n = val.size();for (size_t i = 0; i < n; i++) {if (i)wt(' ');wt(val[i]);}}void print() {wt('\n');}template <class Head, class... Tail> void print(Head &&head, Tail &&...tail) {wt(head);if (sizeof...(Tail))wt(' ');print(forward<Tail>(tail)...);}void __attribute__((destructor)) _d() {flush();}} // namespace fastiousing fastio::flush;using fastio::print;using fastio::read;inline void first(bool i = true) {print(i ? "first" : "second");}inline void Alice(bool i = true) {print(i ? "Alice" : "Bob");}inline void Takahashi(bool i = true) {print(i ? "Takahashi" : "Aoki");}inline void yes(bool i = true) {print(i ? "yes" : "no");}inline void Yes(bool i = true) {print(i ? "Yes" : "No");}inline void No() {print("No");}inline void YES(bool i = true) {print(i ? "YES" : "NO");}inline void NO() {print("NO");}inline void Yay(bool i = true) {print(i ? "Yay!" : ":(");}inline void Possible(bool i = true) {print(i ? "Possible" : "Impossible");}inline void POSSIBLE(bool i = true) {print(i ? "POSSIBLE" : "IMPOSSIBLE");}/*** @brief Fast IO*/#line 3 "sol.cpp"#line 2 "library/Math/fastdiv.hpp"struct FastDiv{using u64=uint64_t;using u128=__uint128_t;constexpr FastDiv():m(),s(),x(){}constexpr FastDiv(int _m):m(_m),s(__lg(m-1)),x(((u128(1)<<(s+64))+m-1)/m){}constexpr int get(){return m;}constexpr friend u64 operator/(u64 n,const FastDiv& d){return (u128(n)*d.x>>d.s)>>64;}constexpr friend int operator%(u64 n,const FastDiv& d){return n-n/d*d.m;}constexpr pair<u64,int> divmod(u64 n)const{u64 q=n/(*this);return {q,n-q*m};}int m,s; u64 x;};/*** @brief Fast Division*/#line 3 "library/Math/dynamic.hpp"struct Fp {using u64 = uint64_t;uint v;static int get_mod() {return _getmod();}static void set_mod(int _m) {bar = FastDiv(_m);}Fp inv() const {int tmp, a = v, b = get_mod(), x = 1, y = 0;while (b) {tmp = a / b, a -= tmp * b;swap(a, b);x -= tmp * y;swap(x, y);}if (x < 0) {x += get_mod();}return x;}Fp() : v(0) {}Fp(ll x) {v = x % get_mod();if (v < 0)v += get_mod();}Fp operator-() const {return Fp() - *this;}Fp pow(ll t) {assert(t >= 0);Fp res = 1, b = *this;while (t) {if (t & 1)res *= b;b *= b;t >>= 1;}return res;}Fp &operator+=(const Fp &x) {v += x.v;if (v >= get_mod())v -= get_mod();return *this;}Fp &operator-=(const Fp &x) {v += get_mod() - x.v;if (v >= get_mod())v -= get_mod();return *this;}Fp &operator*=(const Fp &x) {v = (u64(v) * x.v) % bar;return *this;}Fp &operator/=(const Fp &x) {(*this) *= x.inv();return *this;}Fp operator+(const Fp &x) const {return Fp(*this) += x;}Fp operator-(const Fp &x) const {return Fp(*this) -= x;}Fp operator*(const Fp &x) const {return Fp(*this) *= x;}Fp operator/(const Fp &x) const {return Fp(*this) /= x;}bool operator==(const Fp &x) const {return v == x.v;}bool operator!=(const Fp &x) const {return v != x.v;}friend istream &operator>>(istream &is, Fp &x) {return is >> x.v;}friend ostream &operator<<(ostream &os, const Fp &x) {return os << x.v;}private:static FastDiv bar;static int _getmod() {return bar.get();}};FastDiv Fp::bar(998244353);void rd(Fp &x) {fastio::rd(x.v);}void wt(Fp x) {fastio::wt(x.v);}/*** @brief Dynamic Modint*/#line 2 "library/Math/comb.hpp"template <typename T> T Inv(ll n) {static int md;static vector<T> buf({0, 1});if (md != T::get_mod()) {md = T::get_mod();buf = vector<T>({0, 1});}assert(n > 0);n %= md;while (SZ(buf) <= n) {int k = SZ(buf), q = (md + k - 1) / k;buf.push_back(buf[k * q - md] * q);}return buf[n];}template <typename T> T Fact(ll n, bool inv = 0) {static int md;static vector<T> buf({1, 1}), ibuf({1, 1});if (md != T::get_mod()) {md = T::get_mod();buf = ibuf = vector<T>({1, 1});}assert(n >= 0 and n < md);while (SZ(buf) <= n) {buf.push_back(buf.back() * SZ(buf));ibuf.push_back(ibuf.back() * Inv<T>(SZ(ibuf)));}return inv ? ibuf[n] : buf[n];}template <typename T> T nPr(int n, int r, bool inv = 0) {if (n < 0 || n < r || r < 0)return 0;return Fact<T>(n, inv) * Fact<T>(n - r, inv ^ 1);}template <typename T> T nCr(int n, int r, bool inv = 0) {if (n < 0 || n < r || r < 0)return 0;return Fact<T>(n, inv) * Fact<T>(r, inv ^ 1) * Fact<T>(n - r, inv ^ 1);}// sum = n, r tuplestemplate <typename T> T nHr(int n, int r, bool inv = 0) {return nCr<T>(n + r - 1, r - 1, inv);}// sum = n, a nonzero tuples and b tuplestemplate <typename T> T choose(int n, int a, int b) {if (n == 0)return !a;return nCr<T>(n + b - 1, a + b - 1);}/*** @brief Combination*/#line 2 "library/DataStructure/unionfind.hpp"struct UnionFind{vector<int> par; int n;UnionFind(){}UnionFind(int _n):par(_n,-1),n(_n){}int root(int x){return par[x]<0?x:par[x]=root(par[x]);}bool same(int x,int y){return root(x)==root(y);}int size(int x){return -par[root(x)];}bool unite(int x,int y){x=root(x),y=root(y); if(x==y)return false;if(size(x)>size(y))swap(x,y);par[y]+=par[x]; par[x]=y; n--; return true;}};/*** @brief Union Find*/#line 7 "sol.cpp"using P = pair<int, int>;map<P, vector<int>> mp = {{{1, 1}, {0, 1}},{{1, 2}, {0, 2, 1}},{{1, 3}, {0, 5, 2, 1}},{{1, 4}, {0, 12, 5, 2, 1}},{{1, 5}, {0, 28, 12, 5, 2, 1}},{{1, 6}, {0, 64, 28, 12, 5, 2, 1}},{{1, 7}, {0, 144, 64, 28, 12, 5, 2, 1}},{{1, 8}, {0, 320, 144, 64, 28, 12, 5, 2, 1}},{{1, 9}, {0, 704, 320, 144, 64, 28, 12, 5, 2, 1}},{{1, 10}, {0, 1536, 704, 320, 144, 64, 28, 12, 5, 2, 1}},{{1, 11}, {0, 3328, 1536, 704, 320, 144, 64, 28, 12, 5, 2, 1}},{{1, 12}, {0, 7168, 3328, 1536, 704, 320, 144, 64, 28, 12, 5, 2, 1}},{{1, 13}, {0, 15360, 7168, 3328, 1536, 704, 320, 144, 64, 28, 12, 5, 2, 1}},{{1, 14},{0, 32768, 15360, 7168, 3328, 1536, 704, 320, 144, 64, 28, 12, 5, 2, 1}},{{1, 15},{0, 69632, 32768, 15360, 7168, 3328, 1536, 704, 320, 144, 64, 28, 12, 5, 2,1}},{{1, 16},{0, 147456, 69632, 32768, 15360, 7168, 3328, 1536, 704, 320, 144, 64, 28,12, 5, 2, 1}},{{1, 17},{0, 311296, 147456, 69632, 32768, 15360, 7168, 3328, 1536, 704, 320, 144,64, 28, 12, 5, 2, 1}},{{1, 18},{0, 655360, 311296, 147456, 69632, 32768, 15360, 7168, 3328, 1536, 704,320, 144, 64, 28, 12, 5, 2, 1}},{{1, 19},{0, 1376256, 655360, 311296, 147456, 69632, 32768, 15360, 7168, 3328,1536, 704, 320, 144, 64, 28, 12, 5, 2, 1}},{{1, 20}, {0, 2883584, 1376256, 655360, 311296, 147456, 69632,32768, 15360, 7168, 3328, 1536, 704, 320,144, 64, 28, 12, 5, 2, 1}},{{1, 21}, {0, 6029312, 2883584, 1376256, 655360, 311296, 147456, 69632,32768, 15360, 7168, 3328, 1536, 704, 320, 144,64, 28, 12, 5, 2, 1}},{{1, 22},{0, 12582912, 6029312, 2883584, 1376256, 655360, 311296, 147456,69632, 32768, 15360, 7168, 3328, 1536, 704, 320,144, 64, 28, 12, 5, 2, 1}},{{1, 23},{0, 26214400, 12582912, 6029312, 2883584, 1376256, 655360, 311296,147456, 69632, 32768, 15360, 7168, 3328, 1536, 704,320, 144, 64, 28, 12, 5, 2, 1}},{{1, 24}, {0, 54525952, 26214400, 12582912, 6029312, 2883584, 1376256,655360, 311296, 147456, 69632, 32768, 15360, 7168,3328, 1536, 704, 320, 144, 64, 28,12, 5, 2, 1}},{{1, 25},{0, 113246208, 54525952, 26214400, 12582912, 6029312, 2883584,1376256, 655360, 311296, 147456, 69632, 32768, 15360,7168, 3328, 1536, 704, 320, 144, 64,28, 12, 5, 2, 1}},{{2, 2}, {0, 8, 4, 4, 1}},{{2, 3}, {0, 40, 17, 14, 10, 6, 1}},{{2, 4}, {0, 192, 80, 64, 39, 28, 20, 8, 1}},{{2, 5}, {0, 896, 368, 296, 184, 120, 81, 58, 34, 10, 1}},{{2, 6}, {0, 4096, 1664, 1344, 856, 560, 368, 240, 167, 112, 52, 12, 1}},{{2, 7},{0, 18432, 7424, 6016, 3904, 2568, 1712, 1112, 728, 488, 337, 198, 74, 14,1}},{{2, 8},{0, 81920, 32768, 26624, 17536, 11584, 7816, 5136, 3384, 2208, 1456, 992,647, 324, 100, 16, 1}},{{2, 9},{0, 360448, 143360, 116736, 77824, 51584, 35136, 23304, 15520, 10232, 6704,4392, 2936, 1976, 1169, 498, 130, 18, 1}},{{2, 10}, {0, 1572864, 622592, 507904, 342016, 227328, 156032,104256, 70024, 46640, 30888, 20320, 13304, 8784,5904, 3792, 1991, 728, 164, 20, 1}},{{2, 11},{0, 6815744, 2686976, 2195456, 1490944, 993280, 686080, 461184,311872, 209416, 139968, 93048, 61440, 40328, 26480, 17624,11672, 6952, 3217, 1022, 202, 22, 1}},{{2, 12}, {0, 29360128, 11534336, 9437184, 6455296, 4308992, 2992128,2021376, 1374592, 929088, 625544, 419408, 279656, 185376,122088, 80112, 52888, 35200, 22416, 12160, 4967,1388, 244, 24, 1}},{{3, 3}, {0, 400, 144, 106, 84, 69, 52, 32, 9, 1}},{{3, 4}, {0, 3840, 1360, 952, 705, 550, 445, 360, 270, 164, 62, 12, 1}},{{3, 5},{0, 35840, 12544, 8720, 6408, 4897, 3772, 2972, 2371, 1873, 1385, 854, 376,101, 15, 1}},{{3, 6},{0, 327680, 113664, 78592, 57936, 44456, 34161, 26334, 20329, 15846, 12510,9758, 7131, 4478, 2164, 714, 149, 18, 1}},{{3, 7}, {0, 2949120, 1015808, 699392, 516864, 398928, 308296, 238385,183352, 140476, 108244, 84130, 65926, 50898, 36946, 23558,12123, 4602, 1205, 206, 21, 1}},{{3, 8}, {0, 26214400, 8978432, 6160384, 4561920, 3537664, 2748496,2136040, 1652625, 1269794, 973997, 746362, 574842, 446028,347449, 266040, 192322, 124150, 66909, 28072, 8654,1876, 272, 24, 1}},{{4, 4},{0, 73728, 25600, 17152, 11728, 9040, 7504, 6288, 5340, 4436, 3432, 2360,1296, 492, 116, 16, 1}},{{4, 5}, {0, 1376256, 471040, 314368, 213248, 158976, 128272,105936, 89480, 75998, 64363, 53486, 42473, 31078,19942, 10358, 3972, 1054, 186, 20, 1}},{{4, 6}, {0, 25165824, 8519680, 5668864, 3856384, 2863104, 2288896,1868032, 1553240, 1299184, 1090650, 919360, 774295, 643000,517972, 394544, 274893, 167464, 83894, 32492, 9316,1920, 272, 24, 1}},{{5, 5}, {0, 51380224, 17301504, 11501568, 7749632, 5599232, 4361216,3564416, 3023760, 2603088, 2265120, 1971974, 1703398, 1448460,1194986, 939036, 687581, 454452, 258314, 119182, 42437,11295, 2192, 296, 25, 1}}};int main() {int H, W;ll K, mod;read(H, W, K, mod);if(H>W)swap(H,W);Fp::set_mod(mod);vector<Fp> pw(H * W + 2);rep(x, 1, H * W + 1) pw[x] = Fp(x).pow(K);Fp ret;auto cnt=mp[{H,W}];rep(x,1,H*W+1)ret+=pw[x]*cnt[x];Fp sub;rep(x, 1, H * W + 1) sub += Inv<Fp>(x);ret *= sub;ret /= Fp(2).pow(H * W);print(ret);return 0;}