結果

問題 No.1397 Analog Graffiti
コンテスト
ユーザー 夕叢霧香(ゆうむらきりか)
提出日時 2021-02-14 16:23:47
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,242 bytes
コンパイル時間 1,317 ms
コンパイル使用メモリ 104,100 KB
最終ジャッジ日時 2025-01-18 20:22:44
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2 TLE * 1
other AC * 5 WA * 12 TLE * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<algorithm>
#include<cassert>
#include<iostream>
#include<map>
#include<set>
#include<vector>
using namespace std;
typedef long long lint;
typedef vector<int>vi;
typedef pair<int,int>pii;
#define rep(i,n)for(int i=0;i<(int)(n);++i)
//参考 https://atcoder.jp/contests/tdpc/submissions/3921962

const lint mo=998244353;
const int LIM = 6;
const int LOG_BASE = 4;
 
int W,N;
 
using Key=lint;
map<Key,Key>cache[1<<LIM];

// 0 から W-1 黒
// W から 2W-1 白
pair<vi,int>tovi(Key key){
  vi a(W);
  rep(z,W){
    a[z] = (int)((key >> (z * LOG_BASE)) & ((1 << LOG_BASE) - 1));
  }
  int b=key>>(LOG_BASE*W);
  return make_pair(a,b);
}
Key tokey(vi a,int b){
  // encode
  Key keyNext=0;
  assert(a.size()==W);
  rep(z,W){
    keyNext |= (Key)(a[z]) << (z * LOG_BASE);
  }
  return keyNext|lint(b)<<(LOG_BASE*W);
}
void unify(vi&a,int x,int y){
  int oldx=a[x],oldy=a[y];
  int to=min(oldx,oldy);
  rep(i,a.size())if(a[i]==oldx||a[i]==oldy)a[i]=to;
}
Key trans(Key key,int pat) {
  if(cache[pat].count(key))return cache[pat][key];
  // decode
  auto ab = tovi(key);
  vi a;
  int b;
  tie(a,b)=ab;
  vi chu(2*W);
  int bl=0,wh=W;
  rep(i,W){
    chu[i]=a[i];
    if(a[i]<W)bl=max(bl,a[i]);
    else wh=max(wh,a[i]);
  }
  //すでに黒い部分があった後、再度黒い部分があるのは NG
  if(b>0&&bl==0&&pat>0)return cache[pat][key]=-1;
  rep(i,W)chu[i+W]=(pat&1<<i)?bl++:wh++;
  //unify
  if(chu[W]>=W)chu[W]=W;
  if(chu[2*W-1]>=W)chu[2*W-1]=W;
  rep(j,2)rep(i,W-1)if(chu[j*W+i]/W==chu[j*W+i+1]/W)unify(chu,j*W+i,j*W+i+1);
  rep(i,W)if(chu[i]/W==chu[i+W]/W)unify(chu,i,i+W);

  //繋がらないことが確定した白がある?
  set<int>top;
  rep(i,W)if(chu[i+W]>W)top.insert(chu[i+W]);
  rep(i,W)if(chu[i]>W&&!top.count(chu[i]))return cache[pat][key]=-1;
  //繋がらないことが確定した黒がある?
  top.clear();
  set<int>lft;
  rep(i,W)if(chu[i+W]<W)top.insert(chu[i+W]);
  rep(i,W)if(chu[i]<W&&!top.count(chu[i]))lft.insert(chu[i]);
  if(pat>0&&lft.size())return cache[pat][key]=-1;
  if(pat==0&&lft.size()>1)return cache[pat][key]=-1;
  //新しい頂点の個数は?
  rep(i,W+1){
    int c=0;
    rep(j,2)rep(k,2)c+=(i-k>=0&&i-k<W?chu[j*W+i-k]<W:0);
    if(c%2)b++;
  }
  // renumber
  vi c(chu.begin()+W,chu.end());
  bl=0,wh=W;
  int tr[2*LIM]={};
  rep(i,2*LIM)tr[i]=-1;
  rep(z,W){
    if (tr[c[z]] == -1) {
      tr[c[z]] = c[z]>=W?wh++:bl++;
    }
  }
  rep(z,W){
    c[z] = tr[c[z]];
  }
    
  // encode
  Key keyNext=tokey(c,b);
  cache[pat][key]=keyNext;
  return keyNext;
}
int main(){
  int r,c,n;cin>>r>>c>>n;
  W=c;N=n;
  lint ans=0;
  map<Key,lint>crt;
  vi fst(W);
  rep(i,W){
    fst[i]=W;
  }
  crt[tokey(fst,0)]=1;
  //一段多く。最後は 0
  rep(i,r+1){
    map<Key,lint>nxt;
    rep(pat,1<<W){
      for(auto t:crt){
        Key key;lint val;
        tie(key,val)=t;
        Key to=trans(key,pat);
        if(to<0)continue;
        (nxt[to]+=val)%=mo;
      }
    }
    crt=nxt;
  }
  for(auto t:crt){
    Key key;lint val;
    tie(key,val)=t;
    auto ab=tovi(key);
    vi a;
    int b;
    tie(a,b)=ab;
    cerr<<"a=";
    rep(i,a.size())cerr<<" "<<a[i];
    cerr<<" b="<<b<<" val="<<val<<endl;
    if(a!=fst||b!=N)continue;
    (ans+=val)%=mo;
  }
  cout<<ans<<endl;
}
0