結果

問題 No.1397 Analog Graffiti
コンテスト
ユーザー chocorusk
提出日時 2021-02-24 05:42:58
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 7,800 ms / 10,000 ms
コード長 4,773 bytes
コンパイル時間 4,130 ms
コンパイル使用メモリ 198,304 KB
最終ジャッジ日時 2025-01-19 04:18:11
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#include <list>
#include <atcoder/all>
#define popcount __builtin_popcount
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef pair<int, int> P;
struct unionfind{
    vector<int> par, sz;
    unionfind() {}
    unionfind(int n):par(n), sz(n, 1){
        for(int i=0; i<n; i++) par[i]=i;
    }
    int find(int x){
        if(par[x]==x) return x;
        return par[x]=find(par[x]);
    }
    void unite(int x, int y){
        x=find(x); y=find(y);
        if(x==y) return;
        if(sz[x]>sz[y]) swap(x, y);
        par[x]=y;
        sz[y]+=sz[x];
    }
    bool same(int x, int y){
        return find(x)==find(y);
    }
    int size(int x){
        return sz[find(x)];
    }
};
using mint=modint998244353;
int main()
{
    int r, c, n; cin>>r>>c>>n;
    map<vector<int>, mint> dp[51];
    for(int i=1; i<(1<<c); i++){
        vector<int> v(c+2);
        int t=0;
        for(int j=0; j<c; j++){
            if(i&(1<<j)){
                if(j==0 || !(i&(1<<(j-1)))){
                    t++;
                }
                v[j+1]=t;
            }
        }
        dp[2*t][v]+=1;
    }
    mint ans=0;
    vector<int> v0(c+2);
    for(int z=0; z<r; z++){
        map<vector<int>, mint> ndp[51];
        for(int i=1; i<=n; i++){
            for(auto p:dp[i]){
                auto v=p.first;
                for(int j=0; j<(1<<c); j++){
                    unionfind uf(2*(c+2));
                    uf.unite(0, c+2);
                    uf.unite(c+1, c+1+c+2);
                    for(int k=0; k<c; k++){
                        if(j&(1<<k)){
                            if(v[k+1]>0) uf.unite(k+1, k+1+c+2);
                        }else{
                            if(v[k+1]<=0) uf.unite(k+1, k+1+c+2);
                        }
                    }
                    for(int k=0; k<c; k++){
                        if(j&(1<<k)){
                            if(k && (j&(1<<(k-1)))) uf.unite(k+c+2, k+1+c+2);
                        }else{
                            if(k==0 || !(j&(1<<(k-1)))) uf.unite(k+c+2, k+1+c+2);
                            if(k==c-1) uf.unite(c+c+2, c+1+c+2);
                        }
                    }
                    for(int k=0; k<c+2; k++){
                        for(int l=0; l<k; l++){
                            if(v[k]==v[l]) uf.unite(k, l);
                        }
                    }
                    bool dame=0;
                    for(int k=0; k<c+2; k++){
                        bool ok=0;
                        for(int l=0; l<c+2; l++){
                            if(uf.same(k, l+c+2)){
                                ok=1;
                                break;
                            }
                        }
                        if(!ok){
                            dame=1;
                            break;
                        }
                    }
                    if(j!=0 && dame) continue;
                    int s=0, t=1;
                    vector<int> w(c+2);
                    for(int k=0; k<c+2; k++){
                        bool myon=0;
                        for(int l=0; l<k; l++){
                            if(uf.same(k+c+2, l+c+2)){
                                myon=1;
                                w[k]=w[l];
                                break;
                            }
                        }
                        if(!myon){
                            if(k==0 || k==c+1 || !(j&(1<<(k-1)))) w[k]=s--;
                            else w[k]=t++;
                        }
                    }
                    int cnt=i;
                    for(int k=1; k<c+2; k++){
                        int cnt1=0;
                        if(w[k]>0) cnt1++;
                        if(w[k-1]>0) cnt1++;
                        if(v[k]>0) cnt1++;
                        if(v[k-1]>0) cnt1++;
                        if(cnt1&1) cnt++;
                    }
                    if(j==0){
                        if(cnt==n && *max_element(v.begin(), v.end())==1){
                            ans+=p.second*(r-z);
                        }
                        continue;
                    }
                    if(cnt<=n) ndp[cnt][w]+=p.second;
                }
            }
        }
        for(int i=1; i<=n; i++) swap(dp[i], ndp[i]);
    }
    cout<<ans.val()<<endl;
    return 0;
}
0