Submission #815742

#	Time	Username	Problem	Language	Result	Execution time	Memory
815742		finn__	Chess Rush (CEOI20_chessrush)	C++17	100 / 100	306 ms	16048 KiB

chessrush

#include <bits/stdc++.h>
using namespace std;

constexpr size_t N = 1000;
constexpr int64_t 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; i + j < n; ++j)
                c.m[i][j] = (c.m[i - 1][j - 1] + c.m[0][i + j]) % MOD;

        // Use symmetry to fill the rest
        for (size_t i = 1; i < n; ++i)
            for (size_t j = n - i; j < n; ++j)
                c.m[i][j] = c.m[n - j - 1][n - i - 1];

        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 < c; ++i)
        kpow.m[i][i] = 1;

    for (size_t i = 30; i <= 30; --i)
    {
        kpow.square(c, tmp);
        memcpy(kpow.m, tmp.m, sizeof tmp.m);
        if (((r - 1) >> i) & 1)
            kpow.mul_tridiagonal(c, tmp), memcpy(kpow.m, tmp.m, sizeof tmp.m);
    }

    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)(1LL << 42), (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;
        }
        }
    }
}

Compilation message (stderr)

chessrush.cpp: In function 'int main()':
chessrush.cpp:83:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   83 |     for (size_t i = 0; i < c; ++i)
      |                        ~~^~~

• Subtask 1: 0 / 0
• Subtask 2: 8 / 8
• Subtask 3: 15 / 15
• Subtask 4: 22 / 22
• Subtask 5: 5 / 5
• Subtask 6: 8 / 8
• Subtask 7: 15 / 15
• Subtask 8: 20 / 20
• Subtask 9: 7 / 7