Explanation
Tutorial is loading...
Source
#include <bits/stdc++.h>
using namespace std;
int main() {
int tt;
cin >> tt;
while (tt--) {
int w, d, h;
cin >> w >> d >> h;
int a, b;
cin >> a >> b;
int f, g;
cin >> f >> g;
int ans = b + abs(a - f) + g;
ans = min(ans, a + abs(b - g) + f);
ans = min(ans, (d - b) + abs(a - f) + (d - g));
ans = min(ans, (w - a) + abs(b - g) + (w - f));
cout << ans + h << '\n';
}
return 0;
}
Explanation
Tutorial is loading...
Source 1
#include <bits/stdc++.h>
using namespace std;
int main() {
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
vector<int> cnt(n + 1);
for (int i = 0; i < n; i++) {
int a;
cin >> a;
cnt[a] += 1;
}
int ans = 0;
int sum = 0;
for (int k = 0; k <= n; k++) {
if (cnt[k] == 0 && sum == k) {
ans += 1;
}
sum += cnt[k];
}
cout << ans << '\n';
}
return 0;
}
Source 2
#include <bits/stdc++.h>
using namespace std;
int main() {
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a.begin(), a.end());
int ans = 0;
for (int k = 0; k <= n; k++) {
if (k == 0 || a[k - 1] < k) {
if (k == n || a[k] > k) {
ans += 1;
}
}
}
cout << ans << '\n';
}
return 0;
}
Explanation
Tutorial is loading...
Source
#include <bits/stdc++.h>
using namespace std;
int main() {
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
string s;
cin >> s;
vector<vector<int>> at(26);
for (int i = 0; i < n; i++) {
at[(int) (s[i] - 'a')].push_back(i);
}
vector<int> order(26);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) {
return at[i].size() > at[j].size();
});
string res = "";
int best = -1;
for (int cnt = 1; cnt <= 26; cnt++) {
if (n % cnt == 0) {
int cur = 0;
for (int i = 0; i < cnt; i++) {
cur += min(n / cnt, (int) at[order[i]].size());
}
if (cur > best) {
best = cur;
res = string(n, ' ');
vector<char> extra;
for (int it = 0; it < cnt; it++) {
int i = order[it];
for (int j = 0; j < n / cnt; j++) {
if (j < (int) at[i].size()) {
res[at[i][j]] = (char) ('a' + i);
} else {
extra.push_back((char) ('a' + i));
}
}
}
for (char& c : res) {
if (c == ' ') {
c = extra.back();
extra.pop_back();
}
}
}
}
}
cout << n - best << '\n';
cout << res << '\n';
}
return 0;
}
Explanation
Tutorial is loading...
Source
#include <bits/stdc++.h>
using namespace std;
int main() {
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int ans = 1;
auto Test = [&](long long x) {
int cnt = 0;
for (int v : a) {
long long u = llround(sqrtl(v + x));
if (u * u == v + x) {
cnt += 1;
}
}
ans = max(ans, cnt);
};
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int diff = a[j] - a[i];
for (int k = 1; k * k <= diff; k++) {
if (diff % k == 0) {
long long q = k + diff / k;
if (q % 2 == 0) {
q /= 2;
if (q * q >= a[j]) {
Test(q * q - a[j]);
}
}
}
}
}
}
cout << ans << '\n';
}
return 0;
}
Explanation
Tutorial is loading...
Source
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
vector<int> r1(n), c1(n), r2(n), c2(n);
for (int i = 0; i < n; i++) {
cin >> r1[i] >> c1[i] >> r2[i] >> c2[i];
assert(1 <= r1[i] && r1[i] <= r2[i] && r2[i] <= 2 && c1[i] <= c2[i]);
--c1[i];
}
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) {
return c1[i] < c1[j];
});
set<pair<int, int>> s;
int ans = 0;
int p1 = -1;
int p2 = -1;
for (int i : order) {
if (r1[i] == 1 && r2[i] == 2) {
if (p1 >= c2[i]) {
r1[i] = 2;
}
if (p2 >= c2[i]) {
r2[i] = 1;
}
if (r1[i] > r2[i]) {
continue;
}
}
if (r1[i] == 1 && r2[i] == 2) {
while (!s.empty()) {
auto it = prev(s.end());
if (it->first >= c1[i]) {
c2[it->second] = c1[i];
s.erase(it);
} else {
break;
}
}
ans += (c2[i] - max(c1[i], p1)) + (c2[i] - max(c1[i], p2));
p1 = p2 = c2[i];
s.emplace(c2[i], i);
continue;
}
assert(r1[i] == r2[i]);
if (r1[i] == 1) {
c1[i] = max(c1[i], p1);
p1 = max(p1, c2[i]);
} else {
c1[i] = max(c1[i], p2);
p2 = max(p2, c2[i]);
}
if (c1[i] < c2[i]) {
ans += c2[i] - c1[i];
s.emplace(c2[i], i);
}
}
cout << ans << '\n';
for (int i = 0; i < n; i++) {
++c1[i];
if (r1[i] <= r2[i] && c1[i] <= c2[i]) {
cout << r1[i] << " " << c1[i] << " " << r2[i] << " " << c2[i] << '\n';
} else {
cout << "0 0 0 0" << '\n';
}
}
}
return 0;
}
Explanation
Tutorial is loading...
Source
#include <bits/stdc++.h>
using namespace std;
template <typename T>
T inverse(T a, T m) {
T u = 0, v = 1;
while (a != 0) {
T t = m / a;
m -= t * a; swap(a, m);
u -= t * v; swap(u, v);
}
assert(m == 1);
return u;
}
template <typename T>
class Modular {
public:
using Type = typename decay<decltype(T::value)>::type;
constexpr Modular() : value() {}
template <typename U>
Modular(const U& x) {
value = normalize(x);
}
template <typename U>
static Type normalize(const U& x) {
Type v;
if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
else v = static_cast<Type>(x % mod());
if (v < 0) v += mod();
return v;
}
const Type& operator()() const { return value; }
template <typename U>
explicit operator U() const { return static_cast<U>(value); }
constexpr static Type mod() { return T::value; }
Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
Modular operator-() const { return Modular(-value); }
template <typename U = T>
typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
return *this;
}
Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }
template <typename V, typename U>
friend V& operator>>(V& stream, Modular<U>& number);
private:
Type value;
};
template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename U, typename T>
U& operator<<(U& stream, const Modular<T>& number) {
return stream << number();
}
template <typename U, typename T>
U& operator>>(U& stream, Modular<T>& number) {
typename common_type<typename Modular<T>::Type, long long>::type x;
stream >> x;
number.value = Modular<T>::normalize(x);
return stream;
}
constexpr int md = 998244353;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
Mint p;
cin >> n >> p;
p /= 10000;
vector<vector<Mint>> C(n + 1, vector<Mint>(n + 1));
for (int i = 0; i <= n; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++) {
C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
}
}
vector<vector<Mint>> dp(n + 1, vector<Mint>(n + 1));
vector<vector<Mint>> aux(n + 1, vector<Mint>(n + 1));
for (int b = 0; b <= n; b++) {
dp[0][b] = aux[0][b] = 1;
}
for (int i = 1; i <= n; i++) {
for (int b = 0; b <= n - i; b++) {
for (int y = 0; y <= i - 1; y++) {
dp[i][b] += C[i - 1][y] * aux[i - 1 - y][b] * (dp[y][b + 1] * p + (b == 0 ? 0 : dp[y][b - 1] * (1 - p)));
}
for (int j = 0; j <= i; j++) {
aux[i][b] += dp[j][b] * dp[i - j][b] * C[i][j];
}
}
}
auto ans = dp[n][0];
for (int i = 1; i <= 2 * n; i += 2) {
ans /= i;
}
cout << ans << '\n';
return 0;
}
Explanation
Tutorial is loading...
Source (2nd approach)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
vector<int> p(n);
for (int i = 1; i < n; i++) {
cin >> p[i];
--p[i];
}
for (int i = 2; i <= n; i++) {
if (i == 4 && p[1] == 0 && p[2] == 1 && p[3] == 1) {
cout << 2 << '\n';
} else {
cout << i % 2 << '\n';
}
}
vector<vector<int>> g(n);
for (int i = 1; i < n; i++) {
g[p[i]].push_back(i);
}
string res = "";
auto Solve = [&](int nn) {
vector<vector<vector<bool>>> good(nn);
vector<vector<vector<vector<int>>>> prevs(nn);
vector<int> sz(nn);
vector<int> L(nn);
vector<int> R(nn);
function<void(int)> Dfs = [&](int v) {
sz[v] += 1;
for (int u : g[v]) {
Dfs(u);
sz[v] += sz[u];
}
L[v] = sz[v] / 2;
R[v] = L[v] + 1;
good[v].assign(2, vector<bool>(R[v] - L[v] + 1, false));
prevs[v].assign(2, vector<vector<int>>(R[v] - L[v] + 1));
auto Set = [&](int c, int k, vector<int> pr) {
if (k >= L[v] && k <= R[v]) {
good[v][c][k - L[v]] = true;
prevs[v][c][k - L[v]] = pr;
}
};
if (g[v].size() == 0) {
Set(0, 1, {});
}
if (g[v].size() == 1) {
int u = g[v][0];
for (int cu = 0; cu < 2; cu++) {
for (int ku = L[u]; ku <= R[u]; ku++) {
if (good[u][cu][ku - L[u]]) {
Set(1, 1 + (sz[u] - ku), {cu, ku, 1});
if (cu == 1) {
Set(0, 1 + ku, {cu, ku, 0});
}
}
}
}
}
if (g[v].size() == 2) {
int u = g[v][0];
int w = g[v][1];
for (int cu = 0; cu < 2; cu++) {
for (int ku = L[u]; ku <= R[u]; ku++) {
if (good[u][cu][ku - L[u]]) {
for (int cw = 0; cw < 2; cw++) {
for (int kw = L[w]; kw <= R[w]; kw++) {
if (good[w][cw][kw - L[w]]) {
Set(1, 1 + (sz[u] - ku) + (sz[w] - kw), {cu, ku, 1, cw, kw, 1});
if (cu == 1) {
Set(1, 1 + ku + (sz[w] - kw), {cu, ku, 0, cw, kw, 1});
}
if (cw == 1) {
Set(1, 1 + (sz[u] - ku) + kw, {cu, ku, 1, cw, kw, 0});
}
if (cu == 1 && cw == 1) {
Set(0, 1 + ku + kw, {cu, ku, 0, cw, kw, 0});
}
}
}
}
}
}
}
}
};
Dfs(0);
int best = nn + 1;
int best_k = -1;
for (int k = L[0]; k <= R[0]; k++) {
if (good[0][1][k - L[0]]) {
int val = abs(k - (nn - k));
if (val < best) {
best = val;
best_k = k;
}
}
}
assert(best <= nn);
res = string(nn, '.');
function<void(int, int, int)> Restore = [&](int v, int c, int k) {
int ptr = 0;
for (int u : g[v]) {
res[u] = (prevs[v][c][k - L[v]][ptr + 2] == 0 ? res[v] : (char) ('w' ^ 'b' ^ res[v]));
Restore(u, prevs[v][c][k - L[v]][ptr], prevs[v][c][k - L[v]][ptr + 1]);
ptr += 3;
}
};
res[0] = 'w';
Restore(0, 1, best_k);
return best;
};
Solve(n);
cout << res << '\n';
}
return 0;
}
1782H1 - Window Signals (easy version)
Explanation
Tutorial is loading...
Source for easy version
#include <bits/stdc++.h>
using namespace std;
template <typename T>
T inverse(T a, T m) {
T u = 0, v = 1;
while (a != 0) {
T t = m / a;
m -= t * a; swap(a, m);
u -= t * v; swap(u, v);
}
assert(m == 1);
return u;
}
template <typename T>
class Modular {
public:
using Type = typename decay<decltype(T::value)>::type;
constexpr Modular() : value() {}
template <typename U>
Modular(const U& x) {
value = normalize(x);
}
template <typename U>
static Type normalize(const U& x) {
Type v;
if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
else v = static_cast<Type>(x % mod());
if (v < 0) v += mod();
return v;
}
const Type& operator()() const { return value; }
template <typename U>
explicit operator U() const { return static_cast<U>(value); }
constexpr static Type mod() { return T::value; }
Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
Modular operator-() const { return Modular(-value); }
template <typename U = T>
typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
return *this;
}
Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }
template <typename V, typename U>
friend V& operator>>(V& stream, Modular<U>& number);
private:
Type value;
};
template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template<typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
assert(b >= 0);
Modular<T> x = a, res = 1;
U p = b;
while (p > 0) {
if (p & 1) res *= x;
x *= x;
p >>= 1;
}
return res;
}
template <typename U, typename T>
U& operator<<(U& stream, const Modular<T>& number) {
return stream << number();
}
template <typename U, typename T>
U& operator>>(U& stream, Modular<T>& number) {
typename common_type<typename Modular<T>::Type, long long>::type x;
stream >> x;
number.value = Modular<T>::normalize(x);
return stream;
}
constexpr int md = 998244353;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
int main() {
int tt;
cin >> tt;
while (tt--) {
int h, w, k;
cin >> h >> w >> k;
vector<Mint> fib(h * w + 1);
fib[0] = 1;
fib[1] = 2;
for (int i = 2; i <= h * w; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
vector<pair<int, int>> p(k);
for (int i = 0; i < k; i++) {
cin >> p[i].first >> p[i].second;
--p[i].first; --p[i].second;
}
long long Q = 0;
Mint ans = 0;
for (int ww = 1; ww <= w; ww++) {
for (int hh = 1; hh <= h; hh++) {
for (int top = 0; top < 2; top++) {
for (int bottom = 0; bottom < 2; bottom++) {
for (int left = 0; left < 2; left++) {
for (int right = 0; right < 2; right++) {
int sign = ((top + bottom + left + right) % 2 == 0 ? 1 : -1);
int rh = max(0, hh - top - bottom);
int rw = max(0, ww - left - right);
Q += rh * rw + (h - hh) * (w - ww);
ans += sign * power(Mint(2), rh * rw);
vector<vector<int>> g(hh * ww);
vector<bool> must(hh * ww, false);
bool any = false;
for (int i = 0; i <= h - hh; i++) {
for (int j = 0; j <= w - ww; j++) {
vector<pair<int, int>> here;
for (auto& c : p) {
if (c.first >= i + top && c.first < i + hh - bottom && c.second >= j + left && c.second < j + ww - right) {
here.emplace_back(c.first - i - top, c.second - j - left);
}
}
if (here.size() == 0) {
any = true;
}
if (here.size() == 1) {
int x = here[0].first * rw + here[0].second;
must[x] = true;
}
if (here.size() == 2) {
int x = here[0].first * rw + here[0].second;
int y = here[1].first * rw + here[1].second;
g[x].push_back(y);
g[y].push_back(x);
}
}
}
if (!any) {
Mint ways = 1;
vector<bool> was(rh * rw, false);
for (int i = 0; i < rh * rw; i++) {
if (!was[i] && g[i].empty()) {
was[i] = true;
if (!must[i]) {
ways *= 2;
}
}
}
for (int i = 0; i < rh * rw; i++) {
if (!was[i] && g[i].size() == 1) {
vector<bool> seq;
int x = i;
while (true) {
was[x] = true;
seq.push_back(must[x]);
int to = -1;
for (int y : g[x]) {
if (!was[y]) {
to = y;
break;
}
}
if (to == -1) {
break;
}
x = to;
}
int sz = (int) seq.size();
int beg = 0;
while (beg < sz) {
if (seq[beg]) {
beg += 1;
continue;
}
int end = beg;
while (end + 1 < sz && !seq[end + 1]) {
end += 1;
}
int len = end - beg + 1;
ways *= fib[len];
beg = end + 1;
}
}
}
assert(was == vector<bool>(rh * rw, true));
ans -= sign * ways;
}
}
}
}
}
}
}
cout << ans << '\n';
}
return 0;
}
Source for hard version
#include <bits/stdc++.h>
using namespace std;
template <typename T>
T inverse(T a, T m) {
T u = 0, v = 1;
while (a != 0) {
T t = m / a;
m -= t * a; swap(a, m);
u -= t * v; swap(u, v);
}
assert(m == 1);
return u;
}
template <typename T>
class Modular {
public:
using Type = typename decay<decltype(T::value)>::type;
constexpr Modular() : value() {}
template <typename U>
Modular(const U& x) {
value = normalize(x);
}
template <typename U>
static Type normalize(const U& x) {
Type v;
if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
else v = static_cast<Type>(x % mod());
if (v < 0) v += mod();
return v;
}
const Type& operator()() const { return value; }
template <typename U>
explicit operator U() const { return static_cast<U>(value); }
constexpr static Type mod() { return T::value; }
Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
Modular operator-() const { return Modular(-value); }
template <typename U = T>
typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
return *this;
}
Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }
template <typename V, typename U>
friend V& operator>>(V& stream, Modular<U>& number);
private:
Type value;
};
template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template<typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
assert(b >= 0);
Modular<T> x = a, res = 1;
U p = b;
while (p > 0) {
if (p & 1) res *= x;
x *= x;
p >>= 1;
}
return res;
}
template <typename U, typename T>
U& operator<<(U& stream, const Modular<T>& number) {
return stream << number();
}
template <typename U, typename T>
U& operator>>(U& stream, Modular<T>& number) {
typename common_type<typename Modular<T>::Type, long long>::type x;
stream >> x;
number.value = Modular<T>::normalize(x);
return stream;
}
constexpr int md = 998244353;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
class dsu {
public:
vector<int> p;
vector<int> sz;
int n;
dsu(int _n) : n(_n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
sz.assign(n, 1);
}
inline int get(int x) {
return (x == p[x] ? x : (p[x] = get(p[x])));
}
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x != y) {
p[x] = y;
sz[y] += sz[x];
return true;
}
return false;
}
};
int main() {
int tt;
cin >> tt;
while (tt--) {
int h, w, k;
cin >> h >> w >> k;
vector<Mint> fib(h * w + 1);
fib[0] = 1;
fib[1] = 2;
for (int i = 2; i <= h * w; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
vector<pair<int, int>> p(k);
for (int i = 0; i < k; i++) {
cin >> p[i].first >> p[i].second;
--p[i].first; --p[i].second;
}
Mint ans = 0;
for (int ww = 1; ww <= w; ww++) {
for (int top = 0; top < 2; top++) {
for (int left = 0; left < 2; left++) {
for (int right = 0; right < 2; right++) {
if (ww == 1 && left + right > 0) {
continue;
}
int sign = ((top + left + right) % 2 == 0 ? 1 : -1);
dsu d(h * ww);
vector<vector<int>> g(h * ww);
vector<bool> must(h * ww);
bool done = false;
Mint prod = power(Mint(2), (h - top) * (ww - left - right));
for (int i = 0; i < h; i++) {
for (int j = 0; j <= w - ww; j++) {
vector<pair<int, int>> here;
for (auto& c : p) {
if (c.first >= i + top && c.second >= j + left && c.second < j + ww - right) {
here.emplace_back(c.first - i, c.second - j);
}
}
if (here.size() == 0) {
ans += sign * prod;
done = true;
break;
}
if (here.size() == 1) {
int x = here[0].first * ww + here[0].second;
if (!must[x]) {
must[x] = true;
int px = d.get(x);
prod /= fib[d.sz[px]];
d.sz[px] -= 1;
int sub = 0;
for (int y : g[x]) {
if (!must[y]) {
sub += 1;
}
}
ans += sign * prod * fib[d.sz[px] - sub];
prod *= fib[d.sz[px]];
}
}
if (here.size() == 2) {
int x = here[0].first * ww + here[0].second;
int y = here[1].first * ww + here[1].second;
int px = d.get(x);
int py = d.get(y);
assert(px != py);
prod /= fib[d.sz[px]];
prod /= fib[d.sz[py]];
if (!must[x] && !must[y]) {
int subx = 1;
for (int t : g[x]) {
if (!must[t]) {
subx += 1;
}
}
int suby = 1;
for (int t : g[y]) {
if (!must[t]) {
suby += 1;
}
}
ans += sign * prod * fib[d.sz[px] - subx] * fib[d.sz[py] - suby];
g[x].push_back(y);
g[y].push_back(x);
}
d.unite(px, py);
prod *= fib[d.sz[py]];
}
}
if (done) {
break;
}
for (int j = left; j < ww - right; j++) {
int x = (h - 1 - i) * ww + j;
if (must[x]) {
done = true;
break;
}
int px = d.get(x);
prod /= fib[d.sz[px]];
d.sz[px] -= 1;
prod *= fib[d.sz[px]];
for (int y : g[x]) {
if (!must[y]) {
must[y] = true;
int py = d.get(y);
prod /= fib[d.sz[py]];
d.sz[py] -= 1;
prod *= fib[d.sz[py]];
}
}
}
if (done) {
break;
}
}
}
}
}
}
cout << ans << '\n';
}
return 0;
}
Nice
Editorial is here)
omg tourist Editorial
omg tourist Editorial
omg tourist Editoral
omg tourist Editorial
Do you know why your comment was downvoted? Probably not. Actually, the same comment can be upvoted in a different time/place.
A possible reason is that some random person just randomly downvoted your comment and then some other insane users just continue downvoting without thinking. Toxic, crazy, but this is the reality here.
A simple solution to problem E:
The solution for height = 1 is trivial. I'll discuss about a similar solution for height = 2.
Step 1 : Solve the trivial problem for the rectangle covers both rows only.
Step 2 : Let's detach the rectangles we chose in step 1 into 2 rectangles in the first and second row.
Step 3 : Solve the trivial problem for each rows.
Step 4 : Merge the rectangle in step 2.
Caution: for the rectangles created in step 2, you can only remove or keep them without shrinking.
My submission: 189882008
adu sir thanhchauns2 manh wa
Why are there so few upvotes on this blog?
Why are there so few upvotes on this comment?
I would recommend replacing "Source" with "(Source) Code", at first glance I thought it was the inspiration or the source of the problem :D
what is the fast factorization method in in problem D.
Check all numbers n where n*n<=p and n>=1 where p is the number you want to factor. The factors will always be when p%n==0 and the factors themselves will be n and p/n. This works because when we check all numbers less than or equal to sqrt of p, the following pair(p/n) will get all the numbers greater than or equal to sqrt of p.
This is the general factorization I thought there is faster factorization method possible for this. By the way how to optimize the second part of the problem.
Can anyone please explain C a little bit detailed
We iterate through all the divisors of length N of string, and for each character greedily try to change them so that equal frequencies can be maintained. The greedy idea for constructing the string is explained in the editorial.
Here's a link to my submission, maybe the top submissions would be shorter: https://codeforces.me/contest/1781/submission/206606856
can anyone give hint on how to solve the bonus task of problem $$$D$$$ given in the editorial?
loved your approach @tourist everytime.