Submission #1135219

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135219		onlk97	Chess Rush (CEOI20_chessrush)	C++20	100 / 100	677 ms	568 KiB

chessrush

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
#define double long double
#define x first
#define y second
#define pb push_back
using namespace std;
using namespace __gnu_pbds;
using pii=pair <int,int>;
using tii=pair <pii,int>;
const int mod=1e9+7LL;
int r,c;
int f[2010],inv[2010],finv[2010];
vector <int> mul(vector <int> a,vector <int> b){
    vector <int> res(2*(c+1));
    for (int i=0; i<2*(c+1); i++){
        for (int j=0; j<2*(c+1); j++){
            res[(i+j)%(2*(c+1))]=(res[(i+j)%(2*(c+1))]+a[i]*b[j])%mod;
        }
    }
    return res;
}
vector <int> kans;
void init(){
    f[0]=f[1]=inv[0]=inv[1]=finv[0]=finv[1]=1;
    for (int i=2; i<2010; i++){
        f[i]=f[i-1]*i%mod;
        inv[i]=inv[mod%i]*(mod-mod/i)%mod;
        finv[i]=finv[i-1]*inv[i]%mod;
    }
    vector <int> ans(2*(c+1),0),base(2*(c+1),0);
    ans[0]=1; base[0]=base[1]=base[2*(c+1)-1]=1;
    int p=r-1;
    while (p){
        if (p&1) ans=mul(ans,base);
        p>>=1;
        base=mul(base,base);
    }
    kans=ans;
}
int ncr(int N,int R){
    int ans=1;
    for (int i=1; i<=R; i++) ans=ans*(N-i+1)%mod;
    return ans*finv[R]%mod;
}
void solveP(int st,int en){
    if (st!=en) cout<<"0 0\n";
    else cout<<r-1<<" 1\n";
}
void solveR(int st,int en){
    if (st!=en) cout<<"2 2\n";
    else cout<<"1 1\n";
}
void solveQ(int st,int en){
    if (st==en||abs(st-en)==r-1){
        cout<<"1 1\n";
        return;
    }
    int ans=4;
    if ((st+1)%2==(en+r)%2){
        if (max(st,en)+(r-1-abs(st-en))/2<=c) ans++;
        if (min(st,en)-(r-1-abs(st-en))/2>=1) ans++;
    }
    if (r==c&&(min(st,en)==1||max(st,en)==c)) ans++;
    cout<<"2 "<<ans<<'\n';
}
pii leftB(int st,int en){
    if (st==1) return {1e18,0};
    int moves=(r-1)/(2*(c-1))*2+(st!=c),dir=(st==c?1:-1);
    int xp=1+(r-1)/(2*(c-1))*(2*(c-1)),yp=st;
    while (xp<r||yp!=en){
        if (dir==1&&yp==c){
            dir=-1;
            moves++;
        }
        if (dir==-1&&yp==1){
            dir=1;
            moves++;
        }
        xp++;
        yp+=dir;
    }
    int buf=(xp-r)/2;
    return {moves,ncr(moves+buf-2,buf)};
}
pii rightB(int st,int en){
    if (st==c) return {1e18,0};
    int moves=(r-1)/(2*(c-1))*2+(st!=1),dir=(st==1?-1:1);
    int xp=1+(r-1)/(2*(c-1))*(2*(c-1)),yp=st;
    while (xp<r||yp!=en){
        if (dir==1&&yp==c){
            dir=-1;
            moves++;
        }
        if (dir==-1&&yp==1){
            dir=1;
            moves++;
        }
        xp++;
        yp+=dir;
    }
    int buf=(xp-r)/2;
    return {moves,ncr(moves+buf-2,buf)};
}
void solveB(int st,int en){
    if ((st+1)%2!=(en+r)%2){
        cout<<"0 0\n";
        return;
    }
    if (abs(st-en)==r-1){
        cout<<"1 1\n";
        return;
    }
    pii a=leftB(st,en),b=rightB(st,en);
    if (a>b) swap(a,b);
    if (a.x==b.x) a.y=(a.y+b.y)%mod;
    cout<<a.x<<' '<<a.y<<'\n';
}
void solveK(int st,int en){
    vector <int> vec(2*(c+1),0);
    for (int i=0; i<2*(c+1); i++) vec[(i+st)%(2*(c+1))]=kans[i];
    for (int i=0; i<2*(c+1); i++){
        vec[(i+2*(c+1)-st)%(2*(c+1))]=(vec[(i+2*(c+1)-st)%(2*(c+1))]+mod-kans[i])%mod;
    }
    cout<<r-1<<' '<<vec[en]<<'\n';
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int q;
    cin>>r>>c>>q;
    init();
    while (q--){
        char type;
        int st,en;
        cin>>type>>st>>en;
        if (type=='P') solveP(st,en);
        else if (type=='R') solveR(st,en);
        else if (type=='Q') solveQ(st,en);
        else if (type=='B') solveB(st,en);
        else if (type=='K') solveK(st,en);
    }
}

• 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