432021-01-08 20:34:38mraronChess Rushcpp11Accepted 100/100648ms18204 KiB
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

class bigint {
public:
    bigint(int v = 0);

    bigint &operator=(int v);
    friend bigint operator-(bigint v);

    friend bigint operator+(bigint a, const bigint &b);
    friend bigint operator-(bigint a, const bigint &b);
    bigint operator*(const bigint &v) const;
    bigint operator/(const bigint &v) const;
    
    bigint &operator+=(const bigint &other);
    bigint &operator-=(const bigint &other);
    bigint &operator*=(const bigint &v);
    bigint &operator/=(const bigint &v);

    friend std::istream &operator>>(std::istream &stream, bigint &v);
    friend std::ostream &operator<<(std::ostream &stream, const bigint &v);

private:
    int chkval;
};

void print_answer(const bigint& number_of_steps, const bigint& number_of_ways);


constexpr int P = 1e9+7;

bigint::bigint(int v) { *this = v; }

bigint& bigint::operator=(int v) {
    chkval = ((v % P) + P) % P;
    return *this;
}

bigint& bigint::operator+=(const bigint &other) {
    chkval += other.chkval;
    chkval %= P;
    return *this;
}

bigint operator+(bigint a, const bigint &b) {
    a.chkval += b.chkval;
    a.chkval %= P;
    return a;
}

bigint& bigint::operator-=(const bigint &other) {
    chkval += P - other.chkval;
    chkval %= P;
    return *this;
}

bigint operator-(bigint a, const bigint &b) {
    a.chkval += P - b.chkval;
    a.chkval %= P;
    return a;
}

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);
}

bigint bigint::operator/(const bigint &v) const { 
    bigint ret;
    ret.chkval = (1ll*chkval * modinv(v.chkval)) % P;
    return ret;
}

bigint& bigint::operator*=(const bigint &v) {
    chkval = (1ll*chkval * v.chkval) % P;
    return *this;
}

bigint& bigint::operator/=(const bigint &v) {
    *this = *this / v;
    return *this;
}

bigint operator-(bigint v) {
    if (v.chkval) v.chkval = P - v.chkval;
    return v;
}

istream &operator>>(istream &stream, bigint &v) {
    stream >> v.chkval;
    return stream;
}
ostream &operator<<(ostream &stream, const bigint &v) {
    stream << v.chkval;
    return stream;
}

bigint bigint::operator*(const bigint &v) const {
    bigint res;
    res.chkval = (1ll*chkval * v.chkval) % P;
    return res;
}

void print_answer(const bigint& number_of_steps, const bigint& number_of_ways) {
    cout << number_of_steps << " " << number_of_ways << endl;
}

int Q, R,C, start, finish;
char piece;

const int maxc=1010;
bigint fact[maxc];

void precalc() {
    fact[0] = 1;
    for (int i=1; i<maxc; ++i) {
        fact[i] = fact[i-1] * i;
    }
}
bigint comb(int n, int k) {
    bigint ret = 1;
    for (int x=n-k+1; x<=n; ++x) {
        ret *= x;
    }
    return ret/fact[k];
}

pair<int,bigint> bounce_bishop(int s, int f, int r, int c) {
    pair<int,bigint> ret = { 0,0 };
    if (s!=1) {
        int wallrow = s;
        ret.first = 1+(r-wallrow)/(c-1);
        ret.second = 1;
        int remrow = (r-wallrow)%(c-1);
        bool fromleft=ret.first & 1;
        int impactfield = fromleft ? 1+remrow : c-remrow;
        if (remrow>0) ++ret.first;
        if (impactfield == f) return ret;
        if (remrow==0) ++ret.first;
        int freediag;
        if (fromleft) {
            if (f<impactfield) {
                freediag = c+1-(impactfield+f)/2-1;
                ++ret.first;
            }
            else {
                freediag = (f-impactfield)/2;
            }
        }
        else {
            if (f>impactfield) {
                freediag = (f+impactfield)/2-1;
                ++ret.first;
            }
            else {
                freediag = (impactfield-f)/2;
            }
        }
        ret.second = comb(ret.first-2+freediag,freediag);
    }
    return ret;
}

bigint DPup[maxc][maxc], newDP[maxc][maxc];
vector<bigint> DPright;
void onestep() {
    for (int s=0; s<C; ++s) for (int c=0; c<C; ++c) newDP[s][c]=0;
    for (int s=0; s<C; ++s) for (int c=0; c<C; ++c) {
        if (c>0) newDP[s][c-1] += DPup[s][c];
        newDP[s][c] += DPup[s][c];
        if (c+1<C) newDP[s][c+1] += DPup[s][c];
    }
    for (int s=0; s<C; ++s) for (int c=0; c<C; ++c) DPup[s][c] = newDP[s][c];
}
void doublestep() {
    for (int s=0; s<C; ++s) for (int c=0; c<C; ++c) newDP[s][c]=0;
    for (int s=0; s<C; ++s) {
        for (int mid=0; mid<C; ++mid) {
            newDP[s][0] += DPup[s][mid]*DPup[mid][0];
        }
    }
    for (int e=1; e<C; ++e) newDP[0][e] = newDP[e][0], newDP[C-1][e] = newDP[C-1-e][0];
    for (int e=1; 2*e<C; ++e) {
        for (int s=1; s+1<C; ++s) {
            if (s-e>=0) newDP[s][e] = newDP[s-e][0] + newDP[s+1][e-1];
            else newDP[s][e] = newDP[s+e][0] + newDP[s-1][e-1];
        }
    }
    for (int e=(C-1)/2+1; e<C; ++e) {
        for (int s=1; s+1<C; ++s) {
            newDP[s][e] = newDP[C-1-s][C-1-e];
        }
    }
    for (int s=0; s<C; ++s) for (int c=0; c<C; ++c) DPup[s][c] = newDP[s][c];
}
void kingDP() {
    for (int s=0; s<C; ++s) for (int c=0; c<C; ++c) DPup[s][c] = 0;
    for (int s=0; s<C; ++s) {
        DPup[s][s]=1;
    }
    vector<bool> steplist;
    int r=R-1;
    while (r>0) {
        steplist.push_back(r&1);
        r >>= 1;
    }
    while (!steplist.empty()) {
        if (steplist.back()) onestep();
        steplist.pop_back();
        if (steplist.size()>0) doublestep();
    }

    if (R<C) {
        DPright = vector<bigint>(C,0);
        vector<bigint> DP(R,0); DP[R-1]=1;
        for (int c=1; c<C; ++c) {
            vector<bigint> newDP(R,0);
            for (int r=0; r<R; ++r) {
                if (r>0) newDP[r-1] += DP[r];
                newDP[r] += DP[r];
                if (r+1<R) newDP[r+1] += DP[r];
            }
            DP = newDP;
            DPright[c] = DP[0];
        }
    }
}

pair<int,int> pawnsolve() {
    if (start==finish) return {R-1,1};
    return {0,0};
}
pair<int,int> rooksolve() {
    if (start==finish) return {1,1};
    return {2,2};
}
pair<int,int> queensolve() {
    if (start==finish || finish-start == R-1) return {1,1};
    pair<int,int> ret = {2,2};
    if (start>finish-R+1) ret.second+=2;
    if (start-R+1>0) ret.second++;
    if (finish-R+1>0) ret.second++;
    if (finish+R-1<=C) ret.second++;
    if (start+R-1<=C) ret.second++;
    if ((start+1)%2 == (R+finish)%2) {
        int k = (R+finish-start-1)/2;
        int l = R-k-1;
        if (k>0 && l>0 && start-l>0) ret.second++;
        if (k>0 && l>0 && start+k<=C) ret.second++;
    }
    return ret;
}
pair<int,bigint> bishopsolve() {
    if ((start+1)%2 != (R+finish)%2) return {0,0};
    if (start+R-1 == finish || start-R+1==finish) return {1,1};
    int r=R,c=C;
    if (finish-start+1 > R) r=finish-start+1, c=R, start=1, finish=R;
    int k = (r+finish-start-1)/2;
    int l = r-k-1;
    int cnt = (start-l>0) + (start+k<=c);
    if (k>0 && l>0 && cnt>0) return {2,cnt};
    auto leftans = bounce_bishop(start,finish,r,c);
    auto rightans = bounce_bishop(c+1-start,c+1-finish,r,c);
    if (leftans.first==0 || (rightans.first>0 && leftans.first>rightans.first)) return rightans;
    if (rightans.first==0 || rightans.first>leftans.first) return leftans;
    return {leftans.first, leftans.second+rightans.second};
}
pair<int,bigint> kingsolve() {
    if (finish-start <= R-1) return {R-1, DPup[start-1][finish-1]};
    return {finish-start, DPright[finish-start]};
}

void solve() {
    cin >> piece >> start >> finish;
    if (finish<start) start=C+1-start, finish=C+1-finish;
    pair<int,bigint> ans;
    if (piece=='P') ans = pawnsolve();
    if (piece=='R') ans = rooksolve();
    if (piece=='Q') ans = queensolve();
    if (piece=='B') ans = bishopsolve();
    if (piece=='K') ans = kingsolve();
    cout << ans.first << " " << ans.second << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> R >> C >> Q;
    precalc();
    kingDP();
    while (Q--) solve();
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted8ms17788 KiB
2Accepted268ms17860 KiB
subtask28/8
3Accepted8ms17776 KiB
4Accepted10ms17856 KiB
5Accepted8ms17800 KiB
6Accepted29ms17896 KiB
subtask315/15
7Accepted8ms17816 KiB
8Accepted8ms17900 KiB
9Accepted8ms17820 KiB
10Accepted8ms17880 KiB
subtask422/22
11Accepted207ms17924 KiB
12Accepted79ms17932 KiB
13Accepted9ms17816 KiB
14Accepted540ms17952 KiB
15Accepted9ms17880 KiB
16Accepted13ms17928 KiB
subtask55/5
17Accepted8ms17936 KiB
18Accepted8ms17896 KiB
19Accepted8ms17900 KiB
20Accepted8ms17856 KiB
subtask68/8
21Accepted9ms17920 KiB
22Accepted9ms18008 KiB
23Accepted10ms18024 KiB
24Accepted12ms17944 KiB
subtask715/15
25Accepted10ms18016 KiB
26Accepted9ms18040 KiB
27Accepted14ms18072 KiB
28Accepted14ms17992 KiB
29Accepted9ms18100 KiB
30Accepted8ms18004 KiB
subtask820/20
31Accepted9ms18104 KiB
32Accepted10ms18108 KiB
33Accepted546ms18112 KiB
34Accepted620ms18132 KiB
35Accepted469ms18148 KiB
36Accepted504ms18148 KiB
subtask97/7
37Accepted589ms18168 KiB
38Accepted648ms18184 KiB
39Accepted616ms18188 KiB
40Accepted8ms18200 KiB
41Accepted538ms18204 KiB
42Accepted9ms18136 KiB