結果
問題 | No.2983 Christmas Color Grid (Advent Calender ver.) |
ユーザー | apricity |
提出日時 | 2024-12-08 01:53:17 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 657 ms / 3,340 ms |
コード長 | 11,175 bytes |
コンパイル時間 | 2,152 ms |
コンパイル使用メモリ | 140,304 KB |
実行使用メモリ | 19,712 KB |
最終ジャッジ日時 | 2024-12-08 01:53:25 |
合計ジャッジ時間 | 6,390 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 634 ms
18,816 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 326 ms
13,696 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 2 ms
5,248 KB |
testcase_09 | AC | 177 ms
9,216 KB |
testcase_10 | AC | 8 ms
5,248 KB |
testcase_11 | AC | 2 ms
5,248 KB |
testcase_12 | AC | 3 ms
5,248 KB |
testcase_13 | AC | 2 ms
5,248 KB |
testcase_14 | AC | 2 ms
5,248 KB |
testcase_15 | AC | 3 ms
5,248 KB |
testcase_16 | AC | 3 ms
5,248 KB |
testcase_17 | AC | 3 ms
5,248 KB |
testcase_18 | AC | 3 ms
5,248 KB |
testcase_19 | AC | 9 ms
5,248 KB |
testcase_20 | AC | 18 ms
7,424 KB |
testcase_21 | AC | 50 ms
19,712 KB |
testcase_22 | AC | 32 ms
5,248 KB |
testcase_23 | AC | 192 ms
16,000 KB |
testcase_24 | AC | 23 ms
5,248 KB |
testcase_25 | AC | 323 ms
13,824 KB |
testcase_26 | AC | 23 ms
5,248 KB |
testcase_27 | AC | 657 ms
18,816 KB |
testcase_28 | AC | 284 ms
10,880 KB |
testcase_29 | AC | 28 ms
5,248 KB |
testcase_30 | AC | 198 ms
9,216 KB |
testcase_31 | AC | 7 ms
5,248 KB |
testcase_32 | AC | 15 ms
5,248 KB |
testcase_33 | AC | 35 ms
6,400 KB |
testcase_34 | AC | 2 ms
5,248 KB |
testcase_35 | AC | 2 ms
5,248 KB |
testcase_36 | AC | 3 ms
5,248 KB |
testcase_37 | AC | 3 ms
5,248 KB |
testcase_38 | AC | 3 ms
5,248 KB |
testcase_39 | AC | 3 ms
5,248 KB |
testcase_40 | AC | 1 ms
5,248 KB |
testcase_41 | AC | 2 ms
5,248 KB |
testcase_42 | AC | 2 ms
5,248 KB |
testcase_43 | AC | 2 ms
5,248 KB |
testcase_44 | AC | 2 ms
5,248 KB |
testcase_45 | AC | 2 ms
5,248 KB |
testcase_46 | AC | 2 ms
5,248 KB |
testcase_47 | AC | 2 ms
5,248 KB |
testcase_48 | AC | 2 ms
5,248 KB |
testcase_49 | AC | 2 ms
5,248 KB |
testcase_50 | AC | 2 ms
5,248 KB |
testcase_51 | AC | 2 ms
5,248 KB |
testcase_52 | AC | 2 ms
5,248 KB |
testcase_53 | AC | 2 ms
5,248 KB |
testcase_54 | AC | 2 ms
5,248 KB |
testcase_55 | AC | 2 ms
5,248 KB |
testcase_56 | AC | 2 ms
5,248 KB |
testcase_57 | AC | 2 ms
5,248 KB |
testcase_58 | AC | 2 ms
5,248 KB |
testcase_59 | AC | 2 ms
5,248 KB |
testcase_60 | AC | 1 ms
5,248 KB |
testcase_61 | AC | 2 ms
5,248 KB |
testcase_62 | AC | 2 ms
5,248 KB |
testcase_63 | AC | 2 ms
5,248 KB |
testcase_64 | AC | 2 ms
5,248 KB |
testcase_65 | AC | 2 ms
5,248 KB |
testcase_66 | AC | 2 ms
5,248 KB |
ソースコード
#include<iostream> #include<string> #include<vector> #include<algorithm> #include<numeric> #include<cmath> #include<utility> #include<tuple> #include<array> #include<cstdint> #include<cstdio> #include<iomanip> #include<map> #include<set> #include<unordered_map> #include<unordered_set> #include<queue> #include<stack> #include<deque> #include<bitset> #include<cctype> #include<chrono> #include<random> #include<cassert> #include<cstddef> #include<iterator> #include<string_view> #include<type_traits> #include<functional> #ifdef LOCAL # include "debug_print.hpp" # define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__) #else # define debug(...) (static_cast<void>(0)) #endif using namespace std; namespace io { template <typename T, typename U> istream &operator>>(istream &is, pair<T, U> &p) { is >> p.first >> p.second; return is; } template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; } template <typename T, size_t N = 0> istream &operator>>(istream &is, array<T, N> &v) { for (auto &x : v) is >> x; return is; } template <size_t N = 0, typename T> istream& cin_tuple_impl(istream &is, T &t) { if constexpr (N < std::tuple_size<T>::value) { auto &x = std::get<N>(t); is >> x; cin_tuple_impl<N + 1>(is, t); } return is; } template <class... T> istream &operator>>(istream &is, tuple<T...> &t) { return cin_tuple_impl(is, t); } template<typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) { os << p.first << " " << p.second; return os; } template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { int s = (int)v.size(); for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i]; return os; } template<typename T, size_t N> ostream &operator<<(ostream &os, const array<T, N> &v) { size_t n = v.size(); for (size_t i = 0; i < n; i++) { if (i) os << " "; os << v[i]; } return os; } template <size_t N = 0, typename T> ostream& cout_tuple_impl(ostream &os, const T &t) { if constexpr (N < std::tuple_size<T>::value) { if constexpr (N > 0) os << " "; const auto &x = std::get<N>(t); os << x; cout_tuple_impl<N + 1>(os, t); } return os; } template <class... T> ostream &operator<<(ostream &os, const tuple<T...> &t) { return cout_tuple_impl(os, t); } void in() {} template<typename T, class... U> void in(T &t, U &...u) { cin >> t; in(u...); } void out() { cout << "\n"; } template<typename T, class... U, char sep = ' '> void out(const T &t, const U &...u) { cout << t; if (sizeof...(u)) cout << sep; out(u...); } void outr() {} template<typename T, class... U, char sep = ' '> void outr(const T &t, const U &...u) { cout << t; outr(u...); } void __attribute__((constructor)) _c() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); } } // namespace io using io::in; using io::out; using io::outr; using ll = long long; using D = double; using LD = long double; using P = pair<ll, ll>; using u8 = uint8_t; using u16 = uint16_t; using u32 = uint32_t; using u64 = uint64_t; using i128 = __int128; using u128 = unsigned __int128; using vi = vector<ll>; template <class T> using vc = vector<T>; template <class T> using vvc = vector<vc<T>>; template <class T> using vvvc = vector<vvc<T>>; template <class T> using vvvvc = vector<vvvc<T>>; template <class T> using vvvvvc = vector<vvvvc<T>>; #define vv(type, name, h, ...) \ vector<vector<type>> name(h, vector<type>(__VA_ARGS__)) #define vvv(type, name, h, w, ...) \ vector<vector<vector<type>>> name( \ h, vector<vector<type>>(w, vector<type>(__VA_ARGS__))) #define vvvv(type, name, a, b, c, ...) \ vector<vector<vector<vector<type>>>> name( \ a, vector<vector<vector<type>>>( \ b, vector<vector<type>>(c, vector<type>(__VA_ARGS__)))) template<typename T> using PQ = priority_queue<T,vector<T>>; template<typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>; #define rep1(a) for(ll i = 0; i < a; i++) #define rep2(i, a) for(ll i = 0; i < a; i++) #define rep3(i, a, b) for(ll i = a; i < b; i++) #define rep4(i, a, b, c) for(ll i = a; i < b; i += c) #define overload4(a, b, c, d, e, ...) e #define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__) #define rrep1(a) for(ll i = (a)-1; i >= 0; i--) #define rrep2(i, a) for(ll i = (a)-1; i >= 0; i--) #define rrep3(i, a, b) for(ll i = (b)-1; i >= a; i--) #define rrep4(i, a, b, c) for(ll i = (b)-1; i >= a; i -= c) #define rrep(...) overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__) #define for_subset(t, s) for (ll t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s))) #define ALL(v) v.begin(), v.end() #define RALL(v) v.rbegin(), v.rend() #define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() ) #define SZ(v) ll(v.size()) #define MIN(v) *min_element(ALL(v)) #define MAX(v) *max_element(ALL(v)) #define LB(c, x) distance((c).begin(), lower_bound(ALL(c), (x))) #define UB(c, x) distance((c).begin(), upper_bound(ALL(c), (x))) template <typename T, typename U> T SUM(const vector<U> &v) { T res = 0; for(auto &&a : v) res += a; return res; } template <typename T> vector<pair<T,int>> RLE(const vector<T> &v) { if (v.empty()) return {}; T cur = v.front(); int cnt = 1; vector<pair<T,int>> res; for (int i = 1; i < (int)v.size(); i++) { if (cur == v[i]) cnt++; else { res.emplace_back(cur, cnt); cnt = 1; cur = v[i]; } } res.emplace_back(cur, cnt); return res; } template<class T, class S> inline bool chmax(T &a, const S &b) { return (a < b ? a = b, true : false); } template<class T, class S> inline bool chmin(T &a, const S &b) { return (a > b ? a = b, true : false); } void YESNO(bool flag) { out(flag ? "YES" : "NO"); } void yesno(bool flag) { out(flag ? "Yes" : "No"); } int popcnt(int x) { return __builtin_popcount(x); } int popcnt(u32 x) { return __builtin_popcount(x); } int popcnt(ll x) { return __builtin_popcountll(x); } int popcnt(u64 x) { return __builtin_popcountll(x); } int popcnt_sgn(int x) { return (__builtin_parity(x) & 1 ? -1 : 1); } int popcnt_sgn(u32 x) { return (__builtin_parity(x) & 1 ? -1 : 1); } int popcnt_sgn(ll x) { return (__builtin_parity(x) & 1 ? -1 : 1); } int popcnt_sgn(u64 x) { return (__builtin_parity(x) & 1 ? -1 : 1); } int highbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); } int highbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); } int highbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } int highbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); } int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); } int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); } int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); } template <typename T> T get_bit(T x, int k) { return x >> k & 1; } template <typename T> T set_bit(T x, int k) { return x | T(1) << k; } template <typename T> T reset_bit(T x, int k) { return x & ~(T(1) << k); } template <typename T> T flip_bit(T x, int k) { return x ^ T(1) << k; } template <typename T> T popf(deque<T> &que) { T a = que.front(); que.pop_front(); return a; } template <typename T> T popb(deque<T> &que) { T a = que.back(); que.pop_back(); return a; } template <typename T> T pop(queue<T> &que) { T a = que.front(); que.pop(); return a; } template <typename T> T pop(stack<T> &que) { T a = que.top(); que.pop(); return a; } template <typename T> T pop(PQ<T> &que) { T a = que.top(); que.pop(); return a; } template <typename T> T pop(minPQ<T> &que) { T a = que.top(); que.pop(); return a; } template <typename F> ll binary_search(F check, ll ok, ll ng, bool check_ok = true) { if (check_ok) assert(check(ok)); while (abs(ok - ng) > 1) { ll mid = (ok + ng) / 2; (check(mid) ? ok : ng) = mid; } return ok; } template <typename F> ll binary_search_real(F check, double ok, double ng, int iter = 60) { for (int _ = 0; _ < iter; _++) { double mid = (ok + ng) / 2; (check(mid) ? ok : ng) = mid; } return (ok + ng) / 2; } // max x s.t. b*x <= a ll div_floor(ll a, ll b) { assert(b != 0); if (b < 0) a = -a, b = -b; return a / b - (a % b < 0); } // max x s.t. b*x < a ll div_under(ll a, ll b) { assert(b != 0); if (b < 0) a = -a, b = -b; return a / b - (a % b <= 0); } // min x s.t. b*x >= a ll div_ceil(ll a, ll b) { assert(b != 0); if (b < 0) a = -a, b = -b; return a / b + (a % b > 0); } // min x s.t. b*x > a ll div_over(ll a, ll b) { assert(b != 0); if (b < 0) a = -a, b = -b; return a / b + (a % b >= 0); } // x = a mod b (b > 0), 0 <= x < b ll modulo(ll a, ll b) { assert(b > 0); ll c = a % b; return c < 0 ? c + b : c; } // (q,r) s.t. a = b*q + r, 0 <= r < b (b > 0) // div_floor(a,b), modulo(a,b) pair<ll,ll> divmod(ll a, ll b) { ll q = div_floor(a,b); return {q, a - b*q}; } #include "atcoder/modint.hpp" using mint = atcoder::dynamic_modint<-1>; const int dx[4] = {1,0,-1,0}; const int dy[4] = {0,1,0,-1}; bool memo[1<<25]; int fr[26][26]; bool is_red[25][25]; mint fact[27], finv[27], inv[27], p2[27]; mint com(int n, int k) { if(n < 0 or k < 0 or n < k) return 0; return fact[n] * finv[k] * finv[n-k]; } int main() { int h,w,m; ll k; in(h,w,k,m); mint::set_mod(m); k %= (m-1); fact[0] = fact[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; rep(i,2,h*w+1) { fact[i] = fact[i-1] * i; inv[i] = m - inv[m%i] * (m/i); finv[i] = finv[i-1] * inv[i]; } p2[0] = 1; p2[1] = (m+1)/2; rep(i,1,h*w+1) p2[i] = p2[i-1] * p2[1]; int state = 0; auto dfs = [&] (auto dfs) -> void{ if(memo[state]) return; memo[state] = true; int cr = 0; rep(i,h)rep(j,w) if(!get_bit(state, i*w+j)){ bool valid = false; rep(d,4){ int ni = i + dx[d]; int nj = j + dy[d]; if(ni < 0 or ni >= h or nj < 0 or nj >= w) continue; if(get_bit(state, ni*w+nj)) valid = true; } if(valid) { cr++; state = set_bit(state, i*w+j); dfs(dfs); state = reset_bit(state, i*w+j); } } fr[popcnt(state)][cr]++; }; rep(i,h)rep(j,w){ state = set_bit(state, i*w+j); dfs(dfs); state = reset_bit(state, i*w+j); } mint ans = 0; rep(cg,1,h*w+1) { mint pw = mint(cg).pow(k); rep(cr,h*w-cg+1) if(fr[cg][cr]) { rep(x,cg+1)rep(y,cr+1)rep(p,h*w-cr-cg+1){ mint pre = com(cg,x) * com(cr,y) * com(h*w-cr-cg,p) * fact[x+y+p]; pre *= finv[h*w] * fact[h*w-x-y-p]; ans += pre * pw * inv[h*w-x-y-p+1] * p2[cr+cg] * fr[cg][cr]; } } } out(ans.val()); }