Submission #20484207


Source Code Expand

Copy
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
/*
#include <atcoder/all>
using namespace atcoder;
*/
/*
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
using bll = boost::multiprecision::cpp_int;
using bdouble = boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>;
using namespace boost::multiprecision;
*/
#if defined(LOCAL_TEST) || defined(LOCAL_DEV)
	#define BOOST_STACKTRACE_USE_ADDR2LINE
	#define BOOST_STACKTRACE_ADDR2LINE_LOCATION /usr/local/opt/binutils/bin/addr2line
	#define _GNU_SOURCE 1
	#include <boost/stacktrace.hpp>
#endif
#ifdef LOCAL_TEST
	namespace std {
		template<typename T> class dvector : public std::vector<T> {
		public:
			dvector() : std::vector<T>() {}
			explicit dvector(size_t n, const T& value = T()) : std::vector<T>(n, value) {}
			dvector(const std::vector<T>& v) : std::vector<T>(v) {}
			dvector(const std::initializer_list<T> il) : std::vector<T>(il) {}
			dvector(const std::string::iterator first, const std::string::iterator last) : std::vector<T>(first, last) {}
			dvector(const typename std::vector<T>::iterator first, const typename std::vector<T>::iterator last) : std::vector<T>(first, last) {}
			dvector(const typename std::vector<T>::reverse_iterator first, const typename std::vector<T>::reverse_iterator last) : std::vector<T>(first, last) {}
			dvector(const typename std::vector<T>::const_iterator first, const typename std::vector<T>::const_iterator last) : std::vector<T>(first, last) {}
			dvector(const typename std::vector<T>::const_reverse_iterator first, const typename std::vector<T>::const_reverse_iterator last) : std::vector<T>(first, last) {}
			T& operator[](size_t n) {
				if (this->size() <= n) { std::cerr << boost::stacktrace::stacktrace() << '\n' << "vector::_M_range_check: __n (which is " << n << ") >= this->size() (which is " << this->size() << ")" << '\n'; } return this->at(n);
			}
			const T& operator[](size_t n) const {
				if (this->size() <= n) { std::cerr << boost::stacktrace::stacktrace() << '\n' << "vector::_M_range_check: __n (which is " << n << ") >= this->size() (which is " << this->size() << ")" << '\n'; } return this->at(n);
			}
		};
		template<typename T, typename Compare = less<T>, class Allocator = allocator<T>> class dmultiset : public std::multiset<T,Compare,Allocator> {
		public:
			dmultiset() : std::multiset<T,Compare,Allocator>() {}
			dmultiset(const std::multiset<T,Compare,Allocator>& m) : std::multiset<T,Compare,Allocator>(m) {}
			dmultiset(const std::initializer_list<T> il) : std::multiset<T,Compare,Allocator>(il) {}
			dmultiset(const Compare& comp) : std::multiset<T,Compare,Allocator>(comp) {}
			const typename std::multiset<T,Compare,Allocator>::iterator erase(const typename std::multiset<T,Compare,Allocator>::iterator it) {
				return std::multiset<T,Compare,Allocator>::erase(it);
			}
			size_t erase([[maybe_unused]] const T& x) {
				std::cerr << boost::stacktrace::stacktrace() << '\n'; assert(false);
			}
			size_t erase_all_elements(const T& x) {
				return std::multiset<T,Compare,Allocator>::erase(x);
			}
		};
	}
	class dbool {
	private:
		bool boolvalue;
	public:
		dbool() : boolvalue(false) {}
		dbool(bool b) : boolvalue(b) {}
		operator bool&() { return boolvalue; }
		operator const bool&() const { return boolvalue; }
	};
	#define vector dvector
	#define multiset dmultiset
	#define bool dbool
	class SIGFPE_exception : std::exception {};
	class SIGSEGV_exception : std::exception {};
	void catch_SIGFPE([[maybe_unused]] int e) { std::cerr << boost::stacktrace::stacktrace() << '\n'; throw SIGFPE_exception(); }
	void catch_SIGSEGV([[maybe_unused]] int e) { std::cerr << boost::stacktrace::stacktrace() << '\n'; throw SIGSEGV_exception(); }
	signed convertedmain();
	signed main() { signal(SIGFPE, catch_SIGFPE); signal(SIGSEGV, catch_SIGSEGV); return convertedmain(); }
	#define main() convertedmain()
#else
	#define erase_all_elements erase
#endif
#ifdef LOCAL_DEV
	template<typename T1, typename T2> std::ostream& operator<<(std::ostream& s, const std::pair<T1, T2>& p) {
		return s << "(" << p.first << ", " << p.second << ")"; }
	template <typename T, size_t N> std::ostream& operator<<(std::ostream& s, const std::array<T, N>& a) {
		s << "{ "; for (size_t i = 0; i < N; ++i){ s << a[i] << "\t"; } s << "}"; return s; }
	template<typename T> std::ostream& operator<<(std::ostream& s, const std::set<T>& se) {
		s << "{ "; for (auto itr = se.begin(); itr != se.end(); ++itr){ s << (*itr) << "\t"; } s << "}"; return s; }
	template<typename T> std::ostream& operator<<(std::ostream& s, const std::multiset<T>& se) {
		s << "{ "; for (auto itr = se.begin(); itr != se.end(); ++itr){ s << (*itr) << "\t"; } s << "}"; return s; }
	template<typename T1, typename T2> std::ostream& operator<<(std::ostream& s, const std::map<T1, T2>& m) {
		s << "{\n"; for (auto itr = m.begin(); itr != m.end(); ++itr){ s << "\t" << (*itr).first << " : " << (*itr).second << "\n"; } s << "}"; return s; }
	template<typename T> std::ostream& operator<<(std::ostream& s, const std::deque<T>& v) {
		for (size_t i = 0; i < v.size(); ++i){ s << v[i]; if (i < v.size() - 1) s << "\t"; } return s; }
	template<typename T> std::ostream& operator<<(std::ostream& s, const std::vector<T>& v) {
		for (size_t i = 0; i < v.size(); ++i){ s << v[i]; if (i < v.size() - 1) s << "\t"; } return s; }
	template<typename T> std::ostream& operator<<(std::ostream& s, const std::vector<std::vector<T>>& vv) {
		s << "\\\n"; for (size_t i = 0; i < vv.size(); ++i){ s << vv[i] << "\n"; } return s; }
	void debug_impl() { std::cerr << '\n'; }
	template<typename Head, typename... Tail> void debug_impl(Head head, Tail... tail) { std::cerr << " " << head << (sizeof...(tail) ? "," : ""); debug_impl(tail...); }
	#define debug(...) do { std::cerr << ":" << __LINE__ << " (" << #__VA_ARGS__ << ") ="; debug_impl(__VA_ARGS__); } while (false)
	constexpr inline long long prodlocal([[maybe_unused]] long long prod, [[maybe_unused]] long long local) { return local; }
#else
	#define debug(...) do {} while (false)
	constexpr inline long long prodlocal([[maybe_unused]] long long prod, [[maybe_unused]] long long local) { return prod; }
#endif
//#define int long long
using ll = long long;
//INT_MAX = (1<<31)-1 = 2147483647, INT64_MAX = (1LL<<63)-1 = 9223372036854775807
constexpr ll INF = numeric_limits<ll>::max() == INT_MAX ? (ll)1e9 + 7 : (ll)1e18;
constexpr ll MOD = (ll)1e9 + 7; //primitive root = 5
//constexpr ll MOD = 998244353; //primitive root = 3
constexpr double EPS = 1e-9;
constexpr ll dx[4] = {1, 0, -1, 0};
constexpr ll dy[4] = {0, 1, 0, -1};
constexpr ll dx8[8] = {1, 0, -1, 0, 1, 1, -1, -1};
constexpr ll dy8[8] = {0, 1, 0, -1, 1, -1, 1, -1};
#define rep(i, n)   for(ll i=0, i##_length=(n); i< i##_length; ++i)
#define repeq(i, n) for(ll i=1, i##_length=(n); i<=i##_length; ++i)
#define rrep(i, n)   for(ll i=(n)-1; i>=0; --i)
#define rrepeq(i, n) for(ll i=(n)  ; i>=1; --i)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
void p() { std::cout << '\n'; }
template<typename Head, typename... Tail> void p(Head head, Tail... tail) { std::cout << head << (sizeof...(tail) ? " " : ""); p(tail...); }
template<typename T> inline void pv(std::vector<T>& v) { for(ll i=0, N=v.size(); i<N; i++) std::cout << v[i] << " \n"[i==N-1]; }
template<typename T> inline bool chmax(T& a, T b) { return a < b && (a = b, true); }
template<typename T> inline bool chmin(T& a, T b) { return a > b && (a = b, true); }
template<typename T> inline void uniq(std::vector<T>& v) { v.erase(std::unique(v.begin(), v.end()), v.end()); }
template<typename T> inline ll sz(T& v) { return v.size(); }

/*-----8<-----template-----8<-----*/

//[lib]modint.cpp
map<ll,ll> inv_cache;
struct Modint{
	unsigned long long num = 0;
	constexpr Modint() noexcept {}
	//constexpr Modint(const Modint &x) noexcept : num(x.num){}
	inline constexpr operator ll() const noexcept { return num; }
	inline constexpr Modint& operator+=(Modint x) noexcept { num += x.num; if(num >= MOD) num -= MOD; return *this; }
	inline constexpr Modint& operator++() noexcept { if(num == MOD - 1) num = 0; else num++; return *this; }
	inline constexpr Modint operator++(int) noexcept { Modint ans(*this); operator++(); return ans; }
	inline constexpr Modint operator-() const noexcept { return Modint(0) -= *this; }
	inline constexpr Modint& operator-=(Modint x) noexcept { if(num < x.num) num += MOD; num -= x.num; return *this; }
	inline constexpr Modint& operator--() noexcept { if(num == 0) num = MOD - 1; else num--; return *this; }
	inline constexpr Modint operator--(int) noexcept { Modint ans(*this); operator--(); return ans; }
	inline constexpr Modint& operator*=(Modint x) noexcept { num = (unsigned long long)(num) * x.num % MOD; return *this; }
	inline Modint& operator/=(Modint x) noexcept { return operator*=(x.inv()); }
	template<class T> constexpr Modint(T x) noexcept {
		using U = typename conditional<sizeof(T) >= 4, T, int>::type;
		U y = x; y %= U(MOD); if(y < 0) y += MOD; num = (unsigned long long)(y);
	}
	template<class T> inline constexpr Modint operator+(T x) const noexcept { return Modint(*this) += x; }
	template<class T> inline constexpr Modint& operator+=(T x) noexcept { return operator+=(Modint(x)); }
	template<class T> inline constexpr Modint operator-(T x) const noexcept { return Modint(*this) -= x; }
	template<class T> inline constexpr Modint& operator-=(T x) noexcept { return operator-=(Modint(x)); }
	template<class T> inline constexpr Modint operator*(T x) const noexcept { return Modint(*this) *= x; }
	template<class T> inline constexpr Modint& operator*=(T x) noexcept { return operator*=(Modint(x)); }
	template<class T> inline constexpr Modint operator/(T x) const noexcept { return Modint(*this) /= x; }
	template<class T> inline constexpr Modint& operator/=(T x) noexcept { return operator/=(Modint(x)); }
	inline Modint inv() const noexcept { return inv_cache.count(num) ? inv_cache[num] : inv_cache[num] = inv_calc(); }
	inline constexpr ll inv_calc() const noexcept { ll x = 0, y = 0; extgcd(num, MOD, x, y); return x; }
	static inline constexpr ll extgcd(ll a, ll b, ll &x, ll &y) noexcept { ll g = a; x = 1; y = 0; if(b){ g = extgcd(b, a % b, y, x); y -= a / b * x; } return g; }
	inline constexpr Modint pow(ll x) const noexcept { Modint ans = 1, cnt = x>=0 ? *this : inv(); if(x<0) x = -x; while(x){ if(x & 1) ans *= cnt; cnt *= cnt; x /= 2; } return ans; }
	static inline constexpr ll get_mod() { return MOD; }
};
std::istream& operator>>(std::istream& is, Modint& x){ ll a; is>>a; x = a; return is; }
inline constexpr Modint operator""_M(unsigned long long x) noexcept { return Modint(x); }
std::vector<Modint> fac(1, 1), inv(1, 1);
inline void reserve(size_t a){
	if(fac.size() >= a) return;
	if(a < fac.size() * 2) a = fac.size() * 2;
	if(a >= MOD) a = MOD;
	fac.reserve(a);
	while(fac.size() < a) fac.push_back(fac.back() * Modint(fac.size()));
	inv.resize(fac.size());
	inv.back() = fac.back().inv();
	for(ll i = inv.size() - 1; !inv[i - 1]; i--) inv[i - 1] = inv[i] * i;
}
inline Modint factorial(ll n){ if(n < 0) return 0; reserve(n + 1); return fac[n]; }
inline Modint nPk(ll n, ll r){
    if(r < 0 || n < r) return 0;
    if(n >> 24){ Modint ans = 1; for(ll i = 0; i < r; i++) ans *= n--; return ans; }
    reserve(n + 1); return fac[n] * inv[n - r];
}
inline Modint nCk(ll n, ll r){ if(r < 0 || n < r) return 0; r = min(r, n - r); reserve(r + 1); return inv[r] * nPk(n, r); }
inline Modint nHk(ll n, ll r){ return nCk(n + r - 1, n - 1); } //n種類のものから重複を許してr個選ぶ=玉r個と仕切りn-1個
inline Modint catalan(ll n){ reserve(n * 2 + 1); return fac[n * 2] * inv[n] * inv[n + 1]; }

//[lib]unionfind.cpp
class UnionFind {
public:
	vector<ll> v;
	UnionFind() = default;
	UnionFind(size_t size) : v(size, -1) {}

	ll root(ll x) {
		return (v[x] < 0 ? x : v[x] = root(v[x]));
	}

	bool is_root(ll x) {
		return x == root(x);
	}

	bool is_same(ll x, ll y) {
		return root(x) == root(y);
	}

	bool unite(ll x, ll y) {
		x = root(x);
		y = root(y);
		if (x == y) return false;
		if (v[x] > v[y]) swap(x, y);
		v[x] += v[y];
		v[y] = x;
		return true;
	}

	ll size(ll x) {
		return -v[root(x)];
	}
};
std::ostream& operator<<(std::ostream& s, UnionFind& uf) { 
	for (size_t i = 0; i < uf.v.size(); ++i){ s << uf.v[i]; if (i < uf.v.size() - 1) s << "\t"; } return s;
}

[[nodiscard]] inline ll up(ll bit, ll i) { return bit | (1LL<<i); }
[[nodiscard]] inline ll down(ll bit, ll i) { return bit & ~(1LL<<i); }
[[nodiscard]] inline ll inverse(ll bit, ll i) { return bit ^ (1LL<<i); }
inline bool isup(ll bit, ll i) { return bit & (1LL<<i); }
inline bool isdown(ll bit, ll i) { return !(bit & (1LL<<i)); }
inline ll bsr(ll bit){ assert(bit); return 63 - __builtin_clzll(bit); } //最上位ビットの位置
inline ll bsf(ll bit){ assert(bit); return __builtin_ctzll(bit); } //最下位ビットの位置
//numeric_limits<ll>::digits -> llのビット数の定数
//__builtin_popcountll(bit); -> bitの立っている個数を返す
//__builtin_clzll(bit); -> bitの頭の0の数を返す 0のときは未定義に注意
//__builtin_ctzll(bit); -> bitのお尻の0の数を返す 0のときは未定義に注意
/*
//bitの部分集合を全列挙
for (ll subbit = bit; subbit >= 0; subbit--) {
	subbit &= bit;
	//if(subbit==bit)continue; //全体集合bit自身をスキップ
	//if(subbit==0)continue; //空集合をスキップ
	debug(subbit);
}
*/

/*-----8<-----library-----8<-----*/

constexpr ll H_MAX = 6;
constexpr ll W_MAX = 100;
//constexpr ll MOD = 1'000'000'007;

ll H, W;

void solve() {
	scanf("%lld%lld", &H, &W);

	ll size = 5;
	vector<ll> pw(10);
	pw[0] = 1;
	rep(i, pw.size() - 1) pw[i + 1] = size * pw[i];
	vector<vector<Modint>> dp(W, vector<Modint>(pw[H]));

	/*
		0白
		1黒(0,0と繋がっている)
		2,3,4黒(0,0と繋がっていない && 同じ番号同士繋がっている)
	*/

	auto getstate = [&](ll val, ll index) {
		val/=pw[index];
		return val%size;
	};
	auto setstate = [&](ll val, ll index, ll s) {
		val += pw[index] * s;
		return val;
	};

	//dp初期値
	for (ll bit = 0; bit < (1LL<<H); bit++) {
		if(isdown(bit,0))continue;
		ll val = 1;
		ll label = 1;
		repeq(i, H-1) {
			if (bit & (1LL<<i)) {
				//黒
				val = setstate(val, i, label);
			}else{
				//白
				if(isup(bit,i-1))label++;
			}
		}
		dp[0][val]=1;
	}

	rep(w, W-1) rep(h, pw[H]) {
		//bit:次の白黒状態
		for (ll bit = 0; bit < (1LL<<H); bit++) {
			UnionFind uf(H * 2 + 1);
			{
				vector<vector<ll>> tmp(size);
				rep(i, H) {
					ll s = getstate(h, i);
					if (s == 1) uf.unite(H * 2, i);
					else if(s!=0) tmp[s].push_back(i);
				}
				for(auto&& v:tmp){
					rep(i, sz(v) - 1) uf.unite(v[i], v[i + 1]);
				}
				rep(i, H){
					if(isup(bit,i)){
						if (getstate(h, i) != 0) uf.unite(i, i + H);
						if (isup(bit, i + 1)) uf.unite(i + H, i + 1 + H);
					}
				}
			}
			{
				ll val = 0;
				ll label = 2;
				rep(i, H) {
					if (isdown(bit, i)) {
						if (i > 0 && isup(bit, i - 1)) label++;
						continue;
					}
					if (uf.is_same(H * 2, i + H)) val = setstate(val, i, 1);
					else {
						bool connected = false;
						rep(j, i) {
							if (uf.is_same(j + H, i + H)) {
								connected = true;
								val = setstate(val, i, getstate(val, j));
								break;
							}
						}
						if(!connected){
							val = setstate(val, i, label);
						}
					}
				}
				//debug(uf);
				//debug(h,bit,label,val);
				dp[w + 1][val] += dp[w][h];
			}
		}
	}
	
	debug(dp);
	Modint ans = 0;
	rep(h,pw[H]){
		if(getstate(h,H-1)==1)ans+=dp.back()[h];
	}
	printf("%lld\n", (ll)ans);
	
}

// https://atcoder.jp/contests/tdpc/tasks/tdpc_grid
signed main() {
	solve();
	return 0;
}

Submission Info

Submission Time
Task S - マス目
User kyon2326
Language C++ (GCC 9.2.1)
Score 0
Code Size 15775 Byte
Status TLE
Exec Time 8821 ms
Memory 15508 KB

Compile Error

./Main.cpp: In function ‘void solve()’:
./Main.cpp:256:7: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  256 |  scanf("%lld%lld", &H, &W);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~

Judge Result

Set Name All
Score / Max Score 0 / 7
Status
AC × 6
TLE × 2
Set Name Test Cases
All 00, 01, 02, 03, 04, 05, 90, 91
Case Name Status Exec Time Memory
00 TLE 8821 ms 15508 KB
01 TLE 8821 ms 14792 KB
02 AC 837 ms 4000 KB
03 AC 183 ms 3828 KB
04 AC 12 ms 3640 KB
05 AC 9 ms 3648 KB
90 AC 2 ms 3684 KB
91 AC 201 ms 3920 KB