結果

問題 No.1397 Analog Graffiti
ユーザー leaf_1415
提出日時 2021-02-14 22:19:54
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,911 bytes
コンパイル時間 1,821 ms
コンパイル使用メモリ 107,400 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-22 10:04:38
合計ジャッジ時間 2,628 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other AC * 3 WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#include <utility>
#include <complex>
#define rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)
#define reps(x, s) for(llint (x) = 0; (x) < (llint)(s).size(); (x)++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define all(x) (x).begin(),(x).end()
#define outl(x) cout << x << endl
#define SP << " " << 
#define inf 1e18
#define mod 998244353
using namespace std;
typedef long long llint;
typedef long long ll;
typedef pair<llint, llint> P;
ll h, w, n, S;
ll dp[55][135][55];
ll ns[135][1<<7], add[135][1<<7];
vector<string> vec;
map<string, ll> mp;
string adapt(string s)
{
    map<ll, ll> tmp; ll id = 1;
    for(auto c : s){
        if(c == '0') continue;
        if(tmp.count(c)) continue;
        tmp[c] = id++;
    }
    
    for(auto &c : s) c = tmp[c];
    return s;
}
string s;
void dfs(int p){
    if(p == w+1){
        ll cnt[4] = {}; bool flag[4] = {};
        string t = adapt(s);
        for(auto c : t)cnt[c-'0']++;
        
        rep(i, 1, 3) if(cnt[i] != 0 && cnt[i] != 2) return;
        
        stack<char> stk;
        for(auto c : t){
            if(c == '0') continue;
            if(stk.size() && stk.top() == c) stk.pop();
            else stk.push(c);
        }
        if(stk.size()) return;
        
        mp[t];
        return;
    }
    rep(i, 0, 3){
        s += '0'+i;
        dfs(p+1);
        s.pop_back();
    }
}
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> h >> w >> n;
    dfs(0);
    
    ll id = 0;
    for(auto p : mp) p.second = id++, vec.push_back(p.first);
    //cout << vec.size() << endl;
    S = vec.size();
    
    //for(auto p : mp) cout << p.first << endl;
    //cout << mp.size() << endl;
    
    ll W = 1<<w;
    rep(i, 0, S-1) rep(j, 0, W-1) ns[i][j] = -1;
    
    rep(i, 0, S-1){
        rep(j, 0, W-1){
            ll mx = 0; string s = vec[i];
            for(auto c : s) chmax(mx, (ll)c-'0');
            
            bool flag = true;
            rep(k, 0, w-1){
                if(s[k] == s[k+1] && s[k] != 0 && mx >= 2) flag = false;
            }
            string t;
            rep(k, 0, w) t += '0';
            
            ll id = 10;
            rep(k, 0, w){
                ll deg = 0;
                if(s[k] > '0') deg++;
                if(k < w && (j&(1<<k))) deg++;
                if(k-1 >= 0 && (j&(1<<(k-1)))) deg++;
                if(deg == 3) flag = false;
                if(deg == 2 && s[k] != '0') add[i][j]++;
                if(deg == 1){
                    if(s[k] == '0') t[k] = '0' + (id++)/2, add[i][j]++;
                    else t[k] = s[k];
                }
            }
            
            //cout << t << endl;
            if(flag) ns[i][j] = mp[adapt(t)];
            
            //cout << s << " " << j << " " << ns[i][j] << " " << add[i][j] << endl;
        }
    }
    
    dp[0][0][0] = 1;
    rep(i, 0, h){
        rep(j, 0, S-1){
            if(i > 0 && j == 0) continue;
            rep(k, 0, n){
                rep(l, 0, W-1){
                    if(ns[j][l] == -1) continue;
                    if(k+add[j][k] <= n) (dp[i+1][ns[j][l]][k+add[j][l]] += dp[i][j][k]) %= mod;
                }
            }
        }
    }
    cout << dp[h+1][0][n] << endl;
    
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0