Submission #1314450

#TimeUsernameProblemLanguageResultExecution timeMemory
1314450cpismylifeOwOChess Rush (CEOI20_chessrush)C++20
48 / 100
1367 ms126424 KiB
#include <bits/stdc++.h>
#ifndef cpismylifeOwO
#include "arithmetics.h"
#endif // cpismylifeOwO

using namespace std;

const long long mod = 1e9 + 7;
const int MaxN = 1e3 + 5;
const int MaxLog = 30;

#ifdef cpismylifeOwO
constexpr int P = 1e9+7;

int Add(int a, int b) {
	int ret = a%P;
	ret = (ret<0 ? P+ret : ret) + (b%P);
	return (ret>=0 ? ret%P : ret+P);
}

int Sub(int a, int b) {
	int ret = a%P;
	ret = (ret<0 ? P+ret : ret) - (b%P);
	return (ret>=0 ? ret%P : ret+P);
}

int Mul(int a, int b) {
	int ret = (1ll*(a%P) * (b%P)) % P;
	return (ret<0 ? P+ret : ret);
}

int modpow(int base, int exp, int modulus=P) {
  base %= modulus;
  int result = 1;
  while (exp > 0) {
    if (exp & 1) result = (1ll*result * base) % modulus;
    base = (1ll*base * base) % modulus;
    exp >>= 1;
  }
  return result;
}
int modinv(int a, int modulus=P) {
  return modpow(a,modulus-2);
}

int Div(int a, int b) {
	int ret = b%P;
	ret = (1ll*(a%P) * modinv(ret<0 ? P+ret : ret)) % P;
	return (ret<0 ? P+ret : ret);
}
#endif // cpismylifeOwO

long long r;
int c;
int mat[MaxLog][MaxN][MaxN];
int pre[MaxN][MaxN];
int tmp[MaxN][MaxN];

void Pre()
{
    for (int x = 1; x <= c; x++)
    {
        for (int y = 1; y <= c; y++)
        {
            mat[0][x][y] = (abs(x - y) <= 1);
        }
    }
    for (int w = 1; w < MaxLog; w++)
    {
        for (int x = 1; x <= c; x++)
        {
            mat[w][1][x] = 0;
            for (int y = 1; y <= c; y++)
            {
                mat[w][1][x] = Add(mat[w][1][x], Mul(mat[w - 1][1][y], mat[w - 1][y][x]));
            }
        }
        for (int x = 1; x <= c; x++)
        {
            mat[w][x][1] = 0;
            for (int y = 1; y <= c; y++)
            {
                mat[w][x][1] = Add(mat[w][x][1], Mul(mat[w - 1][x][y], mat[w - 1][y][1]));
            }
        }
        for (int x = 2; x <= c; x++)
        {
            for (int y = 2; x + y <= c + 1; y++)
            {
                mat[w][x][y] = Add(mat[w][x - 1][y - 1], mat[w][1][x + y - 1]);
            }
        }
        for (int x = 2; x <= c; x++)
        {
            for (int y = c - x + 2; y <= c; y++)
            {
                mat[w][x][y] = mat[w][c - x + 1][c - y + 1];
            }
        }
    }
    for (int x = 1; x <= c; x++)
    {
        for (int y = 1; y <= c; y++)
        {
            pre[x][y] = (x == y);
        }
    }
    for (int w = 0; w < MaxLog; w++)
    {
        if ((r - 1) & (1 << w))
        {
            for (int x = 1; x <= c; x++)
            {
                for (int y = 1; y <= c; y++)
                {
                    tmp[x][y] = pre[x][y];
                }
            }
            for (int x = 1; x <= c; x++)
            {
                pre[1][x] = 0;
                for (int y = 1; y <= c; y++)
                {
                    pre[1][x] = Add(pre[1][x], Mul(tmp[1][y], mat[w][y][x]));
                }
            }
            for (int x = 1; x <= c; x++)
            {
                pre[x][1] = 0;
                for (int y = 1; y <= c; y++)
                {
                    pre[x][1] = Add(pre[x][1], Mul(tmp[x][y], mat[w][y][1]));
                }
            }
            for (int x = 2; x <= c; x++)
            {
                for (int y = 2; x + y <= c + 1; y++)
                {
                    pre[x][y] = Add(pre[x - 1][y - 1], pre[1][x + y - 1]);
                }
            }
            for (int x = 2; x <= c; x++)
            {
                for (int y = c - x + 2; y <= c; y++)
                {
                    pre[x][y] = pre[c - x + 1][c - y + 1];
                }
            }
        }
    }
}

char p;
int a, b;

void Inp()
{
    cin >> p >> a >> b;
}

void SolveP(int a, int b)
{
    if (a == b)
    {
        cout << r - 1 << " " << 1 << "\n";
        return;
    }
    cout << 0 << " " << 0 << "\n";
}

void SolveR(int a, int b)
{
    if (a == b)
    {
        cout << 1 << " " << 1 << "\n";
        return;
    }
    cout << 2 << " " << 2 << "\n";
}

void SolveQ(int a, int b)
{
    if (a == b || r == abs(a - b))
    {
        cout << 1 << " " << 1 << "\n";
        return;
    }
    int cnt = 2 + 2 * (r >= abs(a - b)) + (a >= r) + (c - a + 1 >= r) + (b >= r) + (c - b + 1 >= r);
    cnt += (r >= abs(a - b) && ((r - abs(a - b)) & 1) && (((r - abs(a - b)) >> 1) < a));
    cnt += (r >= abs(a - b) && ((r - abs(a - b)) & 1) && (((r - abs(a - b)) >> 1) <= c - a));
    cout << 2 << " " << cnt << "\n";
}

long long C(long long k, long long n)
{
    int res = 1;
    for (int x = 1; x <= k; x++)
    {
        res = Mul(res, (n - x + 1) % mod);
    }
    for (int x = 2; x <= k; x++)
    {
        res = Div(res, x);
    }
    return res;
}

pair<long long, int> calcB(int a, int b)
{
    if (a == 1)
    {
        return make_pair(1e9, 0);
    }
    long long st = (r - a + c - 1) / (c - 1) + 1, p;
    if (st % 2 == 0)
    {
        p = c - (a + (st - 1) * (c - 1) - r);
        if (p == b)
        {
            return make_pair(st, 1);
        }
        if (b < p)
        {
            long long t = ((a + (st - 1) * (c - 1) - r) + (c - b)) / 2;
            return make_pair(st + 1, C(t, t + st - 1));
        }
        long long t = (a + (st - 1) * (c - 1) - r - (c - b)) / 2;
        return make_pair(st, C(t, t + st - 2));
    }
    p = (a + (st - 1) * (c - 1) - r) + 1;
    if (p == b)
    {
        return make_pair(st, 1);
    }
    if (b > p)
    {
        long long t = ((a + (st - 1) * (c - 1) - r) + (b - 1)) / 2;
        return make_pair(st + 1, C(t, t + st - 1));
    }
    long long t = (a + (st - 1) * (c - 1) - r - (b - 1)) / 2;
    return make_pair(st, C(t, t + st - 2));
}

void SolveB(int a, int b)
{
    if ((abs(a - b) & 1) == (r & 1))
    {
        cout << 0 << " " << 0 << "\n";
        return;
    }
    pair<long long, int> res1 = calcB(a, b), res2 = calcB(c - a + 1, c - b + 1);
    if (res1.first < res2.first)
    {
        cout << res1.first << " " << res1.second << "\n";
    }
    else if (res1.first > res2.first)
    {
        cout << res2.first << " " << res2.second << "\n";
    }
    else
    {
        cout << min(res1.first, res2.first) << " " << Add(res1.second, res2.second) << "\n";
    }
}

void SolveK(int a, int b)
{
    cout << r - 1 << " " << pre[a][b] << "\n";
}

void Exc()
{
    if (p == 'P')
    {
        SolveP(a, b);
    }
    else if (p == 'R')
    {
        SolveR(a, b);
    }
    else if (p == 'Q')
    {
        SolveQ(a, b);
    }
    else if (p == 'B')
    {
        SolveB(a, b);
    }
    else
    {
        SolveK(a, b);
    }
}

int main()
{
    //freopen("CHESSRUSH.INP", "r", stdin);
    //freopen("CHESSRUSH.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    cin >> r >> c >> test;
    Pre();
    for (int x = 1; x <= test; x++)
    {
        Inp();
        Exc();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...