結果

問題 No.1397 Analog Graffiti
ユーザー leaf_1415leaf_1415
提出日時 2021-02-14 22:19:54
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,911 bytes
コンパイル時間 2,556 ms
コンパイル使用メモリ 107,808 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-29 15:57:07
合計ジャッジ時間 3,143 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 AC 7 ms
4,376 KB
testcase_09 WA -
testcase_10 AC 2 ms
4,376 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 2 ms
4,376 KB
testcase_25 WA -
testcase_26 WA -
権限があれば一括ダウンロードができます

ソースコード

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;
}
0