Submission #725763

#	Time	Username	Problem	Language	Result	Execution time	Memory
725763		pavement	Semafor (COI20_semafor)	C++17	100 / 100	304 ms	940 KiB

semafor

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define g4(a) get<4>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
using iiiii = tuple<int, int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

using vv = vector<vector<int> >;

const int MOD = 1e9 + 7;
int M, N, K, X, Mpow = 1;

int msk[] = {0b01010, 0b01000, 0b10010, 0b11100, 0b01001, 0b10101, 0b00110, 0b11000, 0b10111, 0b11101};

vv mat_mul(vv a, vv b) {
	assert(a[0].size() == b.size());
	vv c(a.size(), vector<int>(b[0].size(), 0));
	for (int i = 0; i < (int)c.size(); i++)
		for (int j = 0; j < (int)c[0].size(); j++)
			for (int k = 0; k < (int)a[0].size(); k++)
				c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
	return c;
}

vv mat_exp(vv a, int k) {
	assert(a.size() == a[0].size());
	vv r(a.size(), vector<int>(a.size(), 0));
	for (int i = 0; i < (int)r.size(); i++) r[i][i] = 1;
	while (k) {
		if (k & 1ll) r = mat_mul(r, a);
		a = mat_mul(a, a);
		k >>= 1ll;
	}
	return r;
}

vector<int> get_ways(int k) {
	vv curr(5 * M + 1, vector<int>(5 * M + 1, 0));
	for (int i = 0; i <= 5 * M; i++) {
		if (i > 0) curr[i][i - 1] = i;
		if (i < 5 * M) curr[i][i + 1] = 5 * M - i;
	}
	auto res = mat_exp(curr, k);
	vector<int> ret(5 * M + 1, 0);
	for (int i = 0; i <= 5 * M; i++) ret[i] = res[i][0];
	return ret;
}

int diff(int x, int y) {
	int ret = 0;
	for (int k = 0; k < M; k++) {
		ret += __builtin_popcountll(msk[x % 10] ^ msk[y % 10]);
		x /= 10;
		y /= 10;
	}
	return ret;
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> M >> N >> K >> X;
	for (int i = 0; i < M; i++) Mpow *= 10;
	auto ways = get_ways(K);
	vv mat1(Mpow, vector<int>(Mpow, 0));
	for (int i = 0; i < Mpow; i++)
		for (int j = 0; j < Mpow; j++)
			mat1[i][j] = ways[diff(i, j)];
	auto adj = mat_exp(mat1, N / K);
	ways = get_ways(N % K);
	for (int i = 0; i < Mpow; i++) {
		int ans = 0;
		for (int j = 0; j < Mpow; j++)
			ans = (ans + adj[X][j] * ways[diff(i, j)]) % MOD;
		cout << ans << '\n';
	}
}

Compilation message (stderr)

semafor.cpp:79:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   79 | main() {
      | ^~~~

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