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