結果

問題 No.1397 Analog Graffiti
ユーザー evima
提出日時 2021-02-05 08:51:43
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 1,168 ms / 10,000 ms
コード長 3,570 bytes
コンパイル時間 1,773 ms
コンパイル使用メモリ 172,148 KB
実行使用メモリ 84,736 KB
最終ジャッジ日時 2024-07-07 06:37:59
合計ジャッジ時間 12,165 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

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

// Enjoy your stay. Code by evima on 2021/02/05
#include <bits/stdc++.h>
#define LOOPVAR_TYPE long
#define all(x) (x).begin(), (x).end()
#define sz(x) ((LOOPVAR_TYPE)(x).size())
#define foreach(it, X) for(__typeof((X).begin()) it = (X).begin(); it != (X).end(); it++)
#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define _rep(i, n) _rep2(i, 0, n)
#define _rep2(i, a, b) for(LOOPVAR_TYPE i = (LOOPVAR_TYPE)(a); i < (LOOPVAR_TYPE)(b); i++)
#define rep(...) GET_MACRO(__VA_ARGS__, _rep2, _rep)(__VA_ARGS__)
template<class T> bool tomin(T &a, const T &b) { return (b < a) ? (a = b, true) : false; }
template<class T> bool tomax(T &a, const T &b) { return (a < b) ? (a = b, true) : false; }
#define fir first
#define sec second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
const double EPS = 1e-9;
const double PI = 3.141592653589793238462;
const long INF = 1070000000LL;
const long MOD = 998244353LL;
using namespace std;
const int MR = 100, MC = 10, MN = 100;
const int B = MC / 2 + 2;
int R, C, N;
char ch[MR][MC + 1];
vector<int> int2baseB(int n){
    vector<int> ret;
    rep(i, C + 1){
        ret.eb(n % B);
        n /= B;
    }
    return ret;
}
int baseB2int(vector<int> v){
    int ret = 0;
    for(int i = C; i >= 0; --i){
        ret = ret * B + v[i];
    }
    return ret;
}
void normalize(vector<int>& v){
    int to[B + 1] = {}, num = 1;
    for(int& x: v){
        if(x){
            if(!to[x]){
                to[x] = num++;
            }
            x = to[x];
        }
    }
}
unordered_map<int, long> memo[MR + 1][MC + 1][MN + 1][2];
long f(int y, int x, int n, int flag, int state){
    if(n > N) return 0;
    auto it = memo[y][x][n][flag].find(state);
    if(it != memo[y][x][n][flag].end()){
        return it->sec;
    }
    long& ret = memo[y][x][n][flag][state];
    auto v = int2baseB(state);
    vector<int> cnt(B);
    for(int x: v) ++cnt[x];
    if(y == R){
        if(all_of(all(v), [](int x){ return x <= 1; })){
            int m = n + !!v[C];
            rep(i, C){
                m += !!v[i] ^ !!v[i + 1];
            }
            ret = m == N;
        }
    }else if(x == C){
        vector<int> nv(C + 1);
        copy(v.begin(), v.end() - 1, nv.begin() + 1);
        normalize(nv);
        ret = f(y + 1, 0, n + (!!v[C - 1] ^ !!v[C]), flag, baseB2int(nv));
    }else{
        // ab
        // c!
        int a = v[x], b = v[x + 1], c = x ? v[x - 1] : 0;
        int s = !!a + !!b + !!c;
        if(ch[y][x] != '#' && !(!a && b && c || b && cnt[b] == 1 && cnt[0] != C || a && b && cnt[b] == 2 && cnt[0] != C - 1)){    // .
            auto nv = v;
            nv[x] = 0;
            normalize(nv);
            ret += f(y, x + 1, n + s % 2, flag || b && cnt[b] == 1 || a && b && cnt[b] == 2, baseB2int(nv));
        }
        if(ch[y][x] != '.' && !flag && (!(a && !b && !c || !a && b && (b == c)))){   // #
            auto nv = v;
            if(!b && !c){
                nv[x] = B;
            }else if(b && c){
                nv[x] = b;
                rep(i, C + 1){
                    if(nv[i] == c){
                        nv[i] = b;
                    }
                }
            }else if(b){
                nv[x] = b;
            }else{  // c
                nv[x] = c;
            }
            normalize(nv);
            ret += f(y, x + 1, n + (s + 1) % 2, flag, baseB2int(nv));
        }
    }
    return ret %= MOD;
}
int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin >> R >> C >> N;
    cout << f(0, 0, 0, 0, 0) << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0