This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
constexpr size_t N = 100;
constexpr int64_t INF = 1LL << 42, MOD = 1000000007;
template <size_t L>
struct Matrix
{
int64_t m[L][L][2];
Matrix operator*(Matrix const &b) const
{
Matrix c;
for (size_t i = 0; i < L; ++i)
for (size_t j = 0; j < L; ++j)
c.m[i][j][0] = INF, c.m[i][j][1] = 0;
for (size_t i = 0; i < L; ++i)
for (size_t j = 0; j < L; ++j)
for (size_t k = 0; k < L; ++k)
{
if (m[i][k][0] + b.m[k][j][0] < c.m[i][j][0])
c.m[i][j][0] = m[i][k][0] + b.m[k][j][0], c.m[i][j][1] = 0;
if (m[i][k][0] + b.m[k][j][0] == c.m[i][j][0])
c.m[i][j][1] = (c.m[i][j][1] + m[i][k][1] * b.m[k][j][1]) % MOD;
}
return c;
}
array<int64_t[2], L> operator*(array<int64_t[2], L> const &b)
{
array<int64_t[2], L> c;
for (size_t i = 0; i < L; ++i)
c[i][0] = INF, c[i][1] = 0;
for (size_t i = 0; i < L; ++i)
for (size_t j = 0; j < L; ++j)
{
if (m[i][j][0] + b[j][0] < c[i][0])
c[i][0] = m[i][j][0] + b[j][0], c[i][1] = 0;
if (m[i][j][0] + b[j][0] == c[i][0])
c[i][1] = (c[i][1] + m[i][j][1] * b[j][1]) % MOD;
}
return c;
}
};
template <typename T>
T binary_exp(T x, T y)
{
T z = 1;
while (y)
{
if (y & 1)
z = (z * x) % MOD;
x = (x * x) % MOD;
y >>= 1;
}
return z;
}
template <typename T>
T modular_inverse(T x) { return binary_exp(x, MOD - 2); }
Matrix<2 * N> bpow[31];
Matrix<N> kpow[31];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int r, c, q;
cin >> r >> c >> q;
// Build king matrix for king
for (size_t i = 0; i < N; ++i)
for (size_t j = 0; j < N; ++j)
{
kpow[1].m[i][j][0] = INF;
kpow[1].m[i][j][1] = 0;
}
for (int i = 0; i < c; ++i)
for (int j = 0; j < c; ++j)
kpow[1].m[i][j][0] = kpow[1].m[i][j][1] = max(1, abs(i - j));
for (size_t i = 2; i < 31; ++i)
kpow[i] = kpow[i - 1] * kpow[i - 1];
while (q--)
{
char type;
int start, finish;
cin >> type >> start >> finish;
switch (type)
{
case 'P':
{
if (start == finish)
cout << r - 1 << " 1\n";
else
cout << "0 0\n";
break;
}
case 'R':
{
if (start == finish)
cout << "1 1\n";
else
cout << "2 2\n";
break;
}
case 'Q':
{
if (start == finish || abs(start - finish) == (r - 1))
cout << "1 1\n";
else
{
int ans = 4 + (r == c) * ((start == 1 || start == c) + (finish == 1 || finish == c));
if ((r - abs(start - finish)) & 1)
{
int side_space = (r - 1 - abs(start - finish)) / 2;
ans += min(start, finish) - side_space >= 1;
ans += max(start, finish) + side_space <= c;
}
cout << "2 " << ans << '\n';
}
break;
}
case 'B':
{
if (!((r - abs(start - finish)) & 1))
{
cout << "0 0\n";
break;
}
if (abs(start - finish) == r - 1)
{
cout << "1 1\n";
break;
}
// Solve for the case when the first move is to the right, then just swap positions
auto solve_bishop = [&]()
{
if (start == c)
return make_pair((int64_t)INF, (int64_t)0);
int64_t moves = 1 + (r - 1 - (c - start) + c - 2) / (c - 1),
t = (((r - 1 - (c - start)) / (c - 1)) & 1) ? 1 : c;
bool last_dir = t == 1;
t += (last_dir ? 1 : -1) * (r - 1 - (c - 1) * (moves - 2) - (c - start));
if (t == finish)
return make_pair(moves, int64_t(1));
int64_t f;
if ((finish > t && last_dir) || (finish < t && !last_dir))
{
f = abs(t - finish) / 2;
}
else
{
if (last_dir)
f = c - (t + finish) / 2;
else
f = (t + finish) / 2 - 1;
}
int64_t num_ways = 1;
for (int64_t i = 0; i < f; ++i)
num_ways = (num_ways * (moves - 1 + i)) % MOD;
int64_t factorial = 1;
for (int64_t i = 2; i <= f; ++i)
factorial = (factorial * i) % MOD;
num_ways = (num_ways * modular_inverse(factorial)) % MOD;
return make_pair(moves, num_ways);
};
auto [dis_right, ways_right] = solve_bishop();
start = c - start + 1;
finish = c - finish + 1;
auto [dis_left, ways_left] = solve_bishop();
int64_t dis = min(dis_left, dis_right);
int64_t ways = 0;
if (dis == dis_left)
ways += ways_left;
if (dis == dis_right)
ways += ways_right;
cout << dis << ' ' << ways % MOD << '\n';
break;
}
case 'K':
{
array<int64_t[2], N> state;
for (size_t i = 0; i < N; ++i)
state[i][0] = INF, state[i][1] = 0;
state[start - 1][0] = 0;
state[start - 1][1] = 1;
size_t k = r - 1, i = 1;
while (k)
{
if (k & 1)
state = kpow[i] * state;
++i;
k >>= 1;
}
cout << state[finish - 1][0] << ' ' << state[finish - 1][1] << '\n';
break;
}
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |