結果
問題 |
No.2983 Christmas Color Grid (Advent Calender ver.)
|
ユーザー |
|
提出日時 | 2024-12-08 03:55:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 592 ms / 3,340 ms |
コード長 | 1,231 bytes |
コンパイル時間 | 4,316 ms |
コンパイル使用メモリ | 253,068 KB |
最終ジャッジ日時 | 2025-02-26 11:33:57 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 64 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using mint = atcoder::modint; int main(){ int h, w; long long k; int m; cin >> h >> w >> k >> m; mint::set_mod(m); const int r = h * w; vector<int> T(r), cnt(r + 1); for(int y = 0; y < h; y++){ for(int x = 0; x < w; x++){ int v = y * w + x; if(y >= 1) T[v] |= 1 << v - w; if(y + 1 < h) T[v] |= 1 << v + w; if(x >= 1) T[v] |= 1 << v - 1; if(x + 1 < w) T[v] |= 1 << v + 1; } } mint ans, div; vector<bool> used(1 << r); for(int i = 0; i < r; i++) used[1 << i] = true; for(int S = 1; S < (1 << r); S++){ if(!used[S]) continue; int U = S, R = S, b, V; while(R){ R -= b = R & -R; U |= V = T[b = __lg(b)]; while(V){ used[S | V & -V] = true; V -= V & -V; } } cnt[__builtin_popcount(S)] += 1 << (r - __builtin_popcount(U)); } for(int i = 1; i <= r; i++){ ans += mint::raw(cnt[i]) * mint(i).pow(k); div += mint::raw(i).inv(); } ans *= div; ans /= 1 << r; cout << ans.val() << '\n'; }