Submission #1231038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231038		The_Samurai	Chess Rush (CEOI20_chessrush)	C++20	0 / 100	571 ms	1884 KiB

chessrush

#include "bits/stdc++.h"
#include "arithmetics.h"
using namespace std;

constexpr int P = 1e9+7;
int binpow(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 c(int n, int k) {
    k = max(k, n - k);
    int ans = 1;
    for (int i = 1; i <= n - k; i++) ans = Mul(ans, i);
    ans = Div(1, ans);
    for (int i = k + 1; i <= n; i++) ans = Mul(ans, i);
    return ans;
}

int n, m, q;
vector<vector<int>> merge(const vector<vector<int>> &a, const vector<vector<int>> &b) {
    vector ans(m, vector(m, 0));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = 0; k < m; k++) {
                // ans[i][k] += a[i][j] * b[j][k];
                ans[i][k] = Add(ans[i][k], Mul(a[i][j], b[j][k]));
            }
        }
    }
    return ans;
}

int main() {
    cin >> n >> m >> q;
    m = 200;
    int lg = 0;
    while ((1 << lg) <= n) lg++;
    vector dp(lg, vector(m, vector(m, 0)));
    for (int i = 0; i < m; i++) {
        dp[0][i][i] = 1;
        if (i > 0) dp[0][i][i - 1] = 1;
        if (i + 1 < m) dp[0][i][i + 1] = 1;
    }
    for (int i = 1; i < lg; i++) dp[i] = merge(dp[i - 1], dp[i - 1]);
    // for (int i = 0; i < m; i++) {
    //     for (int j = 0; j < m; j++) {
    //         cout << dp[1][i][j] << ' ';
    //     }
    //     cout << endl;
    // }
    vector ans(m, vector(m, 0));
    bool emp = true;
    for (int i = lg - 1; i >= 0; i--) {
        if ((n - 1) >> i & 1) {
            if (emp) ans = dp[i];
            else {
                ans = merge(ans, dp[i]);
            }
            emp = false;
        }
    }

    while (q--) {
        char op;
        int c1, c2;
        cin >> op >> c1 >> c2;
        assert(op == 'K');
        cout << n - 1 << ' ' << ans[c1 - 1][c2 - 1] << '\n';
    }
}

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