結果
問題 | No.2983 Christmas Color Grid (Advent Calender ver.) |
ユーザー |
|
提出日時 | 2024-12-25 08:22:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,468 ms / 3,340 ms |
コード長 | 912 bytes |
コンパイル時間 | 706 ms |
コンパイル使用メモリ | 69,400 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-25 08:23:17 |
合計ジャッジ時間 | 23,571 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 64 |
ソースコード
#include<iostream> #include<cassert> #include<atcoder/modint> using namespace std; using mint=atcoder::modint; int H,W,M; long K; mint pK[26]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>H>>W>>K>>M; mint::set_mod(M); mint ans=0,invsum=0; for(int c=1;c<=H*W;c++) { pK[c]=mint(c).pow(K); invsum+=mint(c).inv(); } int U=0,D=0,L=0,R=0; for(int x=0;x<H;x++)for(int y=0;y<W;y++) { int t=1<<x*W+y; if(x>0)U|=t; if(x+1<H)D|=t; if(y>0)L|=t; if(y+1<W)R|=t; } for(int i=1;i<1<<H*W;i++) { if(!(i&1)&&i>>H*W-1&1)continue; int t=i; mint c=0; while(t) { int v=t&-t; while(true) { int w=v; w|=(v&U)>>W; w|=(v&D)<<W; w|=(v&L)>>1; w|=(v&R)<<1; w&=t; if(v==w)break; v=w; } t^=v; c+=pK[__builtin_popcount(v)]; } ans+=c; if(i&1&&!(i>>H*W-1&1))ans+=c; } ans*=invsum; ans/=mint(2).pow(H*W); cout<<ans.val()<<endl; }