Submission #1186165

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186165		Unforgettablepl	Chess Rush (CEOI20_chessrush)	C++20	28 / 100	2096 ms	23980 KiB

chessrush

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

#define int long long

const int modulo = 1e9+7;


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int R,C,Q;
    cin >> R >> C >> Q;
    vector<vector<int>> DPbase(C+2,vector<int>(C+2));
    for(int i=1;i<=C;i++)DPbase[i][i]=1;
    auto combine = [&](vector<vector<int>> &DP1,vector<vector<int>> &DP2){
        vector<vector<int>> DP(C+2,vector<int>(C+2));
        for(int inp=1;inp<=C;inp++){
            for(int outp=1;outp<=C;outp++){
                for(int k=1;k<=C;k++){
                    DP[inp][outp]+=DP1[inp][k]*DP2[k][outp];
                    DP[inp][outp]%=modulo;
                    DP[inp][outp]+=DP1[inp][k-1]*DP2[k][outp];
                    DP[inp][outp]%=modulo;
                    DP[inp][outp]+=DP1[inp][k+1]*DP2[k][outp];
                    DP[inp][outp]%=modulo;
                }
            }
        }
        return DP;
    };
    function<vector<vector<int>>(int)> solve = [&](int x){
        if(x==1)return DPbase;
        int mid = x>>1;
        auto curr = solve(mid);
        curr = combine(curr,curr);
        if(x&1)curr=combine(DPbase,curr);
        return curr;
    };
    auto ans = solve(R);
    for(int i=1;i<=Q;i++){
        char t;int st,ta;cin>>t>>st>>ta;
        cout << max(abs(ta-st),R-1) << ' ' << ans[st][ta] << '\n';
    }
}

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