Submission #480867

#	Time	Username	Problem	Language	Result	Execution time	Memory
480867		hollwo_pelw	Semafor (COI20_semafor)	C++17	100 / 100	424 ms	588 KiB

semafor

/*
// is short or still long ???
hollwo_pelw's template(short)
// Note : -Dhollwo_pelw_local
*/

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;

void FAST_IO(string filein = "", string fileout = "", string fileerr = ""){
	if (fopen(filein.c_str(), "r")){
		freopen(filein.c_str(), "r", stdin);
		freopen(fileout.c_str(), "w", stdout);
#ifdef hollwo_pelw_local
		freopen(fileerr.c_str(), "w", stderr);
#endif
	}
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
}

void Hollwo_Pelw();

signed main(){
#ifdef hollwo_pelw_local
	FAST_IO("input.inp", "output.out", "error.err");
	auto start = chrono::steady_clock::now();
#else
	FAST_IO("semafor.inp", "semafor.out");
#endif
	int testcases = 1;
	// cin >> testcases;
	for (int test = 1; test <= testcases; test++){
		// cout << "Case #" << test << ": ";
		Hollwo_Pelw();
	}
#ifdef hollwo_pelw_local
	auto end = chrono::steady_clock::now();
	cout << "\nExcution time : " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif
	return 0;
}

#define defop(type, op) \
	friend inline type operator op (type a, const type &b) { return a op##= b; } \
	type& operator op##= (const type &oth)
 
template<class T> struct mod_int {
	constexpr int mod() { return T::mod; }
 
	int v;
	mod_int(long long _v = 0) 
		: v(norm(_v)) {}
	
	inline int norm(long long a) {
		return a < 0 ? a % mod() + mod() : a % mod();
	}
	mod_int neg() const { return v == 0 ? 0 : mod() - v; }
	
	template <typename U>
	explicit operator U() const { return v; }
 
	mod_int operator - () const { return neg(); }
	mod_int operator + () const { return mod_int(*this); }
 
	mod_int& operator -- () { if (v == 0) v = mod(); -- v; return *this; }
	friend mod_int operator -- (mod_int& a, int) { mod_int r = a; --a; return r; }
	mod_int& operator ++ () { ++ v; if (v == mod()) v = 0; return *this; }
	friend mod_int operator ++ (mod_int& a, int) { mod_int r = a; ++a; return r; }
	
	defop(mod_int, +) {
		if ((v += oth.v) >= mod()) v -= mod();
		return *this;
	}
	defop(mod_int, -) {
		if ((v -= oth.v) < 0) v += mod();
		return *this;
	}
	defop(mod_int, *) {
		return *this = norm(1ll * v * oth.v);
	}
 
	mod_int pow(long long b) const {
		mod_int a = *this, r = 1;
		while (b) {
			if (b&1) r *= a;
			b >>= 1; a *= a;
		}
		return r;
	}
	mod_int inv() const { return pow(mod() - 2); }
 
	defop(mod_int, /) { 
		return *this *= oth.inv();
	}
 
#define compare(op) friend bool operator op \
(const mod_int& lhs, const mod_int& rhs) { return lhs.v op rhs.v; }
	compare(==) compare(!=) compare(<) compare(<=) compare(>) compare(>=)
#undef compare
 
	friend std::ostream& operator << (std::ostream& out, const mod_int& n) { return out << int(n); }
	friend std::istream& operator >> (std::istream& inp, mod_int& n) { long long x; inp >> x; n = mod_int(x); return inp; }
};
 
struct modular { static constexpr int mod = static_cast<int>(1e9 + 7); };
 
// struct modular { static int mod; };
// int modular::mod;
 
using Mint = mod_int<modular>;

struct matrix {
	vector<vector<Mint>> a;
	
	size_t size() { return a.size(); }

	vector<Mint>& operator [] (int x) {return a[x];}
	const vector<Mint>& operator [] (int x) const {return a[x];}

	matrix(int sz = 0, int v = 0) {
		a.assign(sz, vector<Mint>(sz));
		if (v) for (int i = 0; i < sz; i++) a[i][i] = v;
	}
};

matrix operator * (matrix a, matrix b) {
	int sz = a.size();
	
	matrix c(sz);
	for (int i = 0; i < sz; i++) {
		for (int j = 0; j < sz; j++) {
			for (int k = 0; k < sz; k++)
				c[i][j] += a[i][k] * b[k][j];
		}
	}

	return c;
}

matrix operator ^ (matrix a, int64_t b) {
	int sz = a.size();
	
	matrix r(sz, 1);
	while (b) {
		if (b&1) r = r * a;
		b >>= 1; a = a * a;
	}

	return r;
}

const int num[10] = {
	0b01010, // 0
	0b00010, // 1
	0b01001, // 2
	0b00111, // 3
	0b10010, // 4
	0b10101, // 5
	0b01100, // 6
	0b00011, // 7
	0b11101, // 8
	0b10111  // 9
};

int m, x, d, cnt;
int64_t n, k;

inline int tomask(int v) {
	return m == 1 ? num[v] : num[v % 10] << 5 | num[v / 10];
}

inline int dist(int a, int b) {
	return __builtin_popcount(tomask(a) ^ tomask(b));
}

matrix get_tran(const matrix& a) {
	matrix base(cnt);
	for (int i = 0; i < cnt; i++)
		for (int j = 0; j < cnt; j++)
			base[i][j] = a[0][dist(i, j)];
	return base;
}

void Hollwo_Pelw() {
	cin >> m >> n >> k >> x;
	cnt = m == 1 ? 10 : 100, d = m * 5;
	
	// free move in kth period

	matrix base(d + 1);
	for (int i = 0; i < d; i++) {
		base[i][i + 1] = i + 1;
		base[i + 1][i] = d - i;
	}
	matrix full = base ^ k;
	matrix left = base ^ (n % k);

	matrix res = (get_tran(full) ^ (n / k)) * get_tran(left);
	for (int i = 0; i < cnt; i++)
		cout << res[x][i] << '\n';
}

Compilation message (stderr)

semafor.cpp: In function 'void FAST_IO(std::string, std::string, std::string)':
semafor.cpp:18:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |   freopen(filein.c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
semafor.cpp:19:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |   freopen(fileout.c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 15 / 15
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 15 / 15
• Subtask 6: 40 / 40