#include <bits/stdc++.h>
using namespace std;
constexpr size_t N = 1000;
constexpr int64_t INF = 1LL << 42, MOD = 1000000007;
template <size_t L>
struct Matrix
{
int64_t m[L][L];
void square(size_t n, Matrix &c) const
{
memset(c.m, 0, sizeof c.m);
// Fill first row.
for (size_t j = 0; j < n; ++j)
for (size_t k = 0; k < n; ++k)
c.m[0][j] = (c.m[0][j] + m[0][k] * m[k][j]) % MOD;
// Use very obscure recurrence f_ij = f_i-1,j-1 + f_0,i+j to fill upper triangle.
for (size_t i = 1; i < n; ++i)
for (size_t j = i; j < n; ++j)
c.m[i][j] = (c.m[i - 1][j - 1] + (i + j < n ? c.m[0][i + j] : 0)) % MOD;
// Use symmetry to fill the rest
for (size_t i = 1; i < n; ++i)
for (size_t j = 0; j < i; ++j)
c.m[i][j] = c.m[j][i];
}
void mul_tridiagonal(size_t n, Matrix &c) const
{
memset(c.m, 0, sizeof c.m);
// For a 1 at (i, j), add j-th row of m to i-th row of c
for (size_t i = 0; i < n; ++i)
for (size_t j = i ? (i - 1) : 0; j < min(i + 2, n); ++j)
for (size_t k = 0; k < n; ++k)
c.m[i][k] += m[j][k];
for (size_t i = 0; i < n; ++i)
for (size_t j = 0; j < n; ++j)
c.m[i][j] %= MOD;
}
};
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<N> kpow, tmp;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int r, c, q;
cin >> r >> c >> q;
// Build matrix for king
for (size_t i = 0; i < N; ++i)
kpow.m[i][i] = 1;
for (size_t i = 30; i <= 30; --i)
{
kpow.square(c, tmp);
swap(kpow, tmp);
if (((r - 1) >> i) & 1)
kpow.mul_tridiagonal(c, tmp), swap(kpow, tmp);
}
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 - 2) / (c - 1) - 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
{
++moves;
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':
{
cout << r - 1 << ' ' << kpow.m[start - 1][finish - 1] << '\n';
break;
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
105 ms |
23780 KB |
Output is correct |
| 2 |
Incorrect |
269 ms |
23792 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
90 ms |
23776 KB |
Output is correct |
| 2 |
Correct |
116 ms |
23792 KB |
Output is correct |
| 3 |
Correct |
83 ms |
23780 KB |
Output is correct |
| 4 |
Correct |
137 ms |
23796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
93 ms |
23780 KB |
Output is correct |
| 2 |
Correct |
97 ms |
23792 KB |
Output is correct |
| 3 |
Correct |
92 ms |
23764 KB |
Output is correct |
| 4 |
Correct |
89 ms |
23784 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
93 ms |
23780 KB |
Output is correct |
| 2 |
Correct |
97 ms |
23792 KB |
Output is correct |
| 3 |
Correct |
92 ms |
23764 KB |
Output is correct |
| 4 |
Correct |
89 ms |
23784 KB |
Output is correct |
| 5 |
Correct |
332 ms |
23824 KB |
Output is correct |
| 6 |
Correct |
174 ms |
23792 KB |
Output is correct |
| 7 |
Correct |
117 ms |
23764 KB |
Output is correct |
| 8 |
Correct |
399 ms |
23792 KB |
Output is correct |
| 9 |
Correct |
135 ms |
23788 KB |
Output is correct |
| 10 |
Correct |
123 ms |
23792 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
99 ms |
23776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
99 ms |
23776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
99 ms |
23776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
99 ms |
23776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
105 ms |
23780 KB |
Output is correct |
| 2 |
Incorrect |
269 ms |
23792 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
