[CEOI 2020] 象棋世界

· · 题解

大家 K 的 Case 其实有点推麻烦了，其实最难的是 B？

然后对于 B 来说，为了保证你的跳跃次数尽可能少，你每一次一定跳得尽量极端，除非你下一步可以直达终点。

所以先模拟求出最短路径形态：我们枚举第一次跳跃的方向，然后不断跳极端，找到在你这条路径上第一个 x\geq n,y=c_R 的位置作为暂定终点。

然后考虑再在上面调整，每一次可以让一个拐角少走一步，终点向下平移两步。那么这就是一个插板的组合数。

对于 K 来说，由于 R\geq C，然后你每次最多往上一行，所以你一定恰好走 R-1 步。

于是你需要计算一个“两条线问题”：从 (1,c_1) 游走到 (R,c_R)，不能触碰 x=0 和 x=C+1 两条线的方案数。

这是这道题的一维情况。这很经典，你施加反射容斥，然后你只需要考虑计算到达横坐标 \equiv \pm c_R \pmod {2C+2} 的点的方案数。

这相当于计算 (x+\frac{1}{x}+1)^{R-1} 在 \bmod (x^{2C+2}-1) 循环卷积意义下的结果。这道题没有 NTT 模数所以你不得不暴力卷积得到 O(n^2 \log n) 的复杂度。才不写 MTT 呢。

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
int read(){
    char c=getchar();int x=0;
    while(!isdigit(c)) c=getchar();
    do x=(x<<1)+(x<<3)+(c^48),c=getchar();
    while(isdigit(c));
    return x;
}
const int N=1003,P=1000000007;
int n,m,q,lim;
typedef long long ll;
int qp(int a,int b=P-2){
    int res=1;
    while(b){
        if(b&1) res=(ll)res*a%P;
        a=(ll)a*a%P;b>>=1;
    }
    return res;
}
struct Poly{
    int f[N<<1];
    friend Poly operator*(const Poly x,const Poly y){
        Poly z;
        for(int i=0;i<lim;++i) z.f[i]=0;
        for(int i=0;i<lim;++i)
            for(int j=0;j<lim;++j){
                int t=i+j;
                if(t>=lim) t-=lim;
                z.f[t]=(z.f[t]+(ll)x.f[i]*y.f[j])%P;
            }
        return z;
    }
}F,G;
int fac[N],fiv[N];
int C(int a,int b){
    int res=fiv[b];
    for(int i=0;i<b;++i) res=(ll)res*(a-i)%P;
    return res;
}
void solve(){
    char c=getchar();
    while(!isupper(c)) c=getchar();
    int x=read(),y=read();
    if(c=='P'){
        if(x!=y) puts("0 0");
        else printf("%d 1\n",n-1);
        return;
    }
    if(c=='R'){
        if(x==y) puts("1 1");
        else puts("2 2");
        return;
    }
    if(c=='Q'){
        if(n==m&&((x==1&&y==m)||(x==m&&y==1))) puts("1 1");
        else if(x==y) puts("1 1");
        else{
            int res=4;
            if((x^y^n)&1){
                if(x+y+n-1<=m+m) ++res;
                if(x+y-n+1>=2) ++res;
            }
            if(n==m){
                if(x==1||x==m) ++res;
                if(y==1||y==m) ++res;
            }
            printf("2 %d\n",res);
        }
        return;
    }
    if(c=='K'){
        int a=(y-x+lim)%lim;
        int b=(-x-y+lim)%lim;
        int res=F.f[a]-F.f[b];
        if(res<0) res+=P;
        printf("%d %d\n",n-1,res);
        return;
    }
    if(c=='B'){
        if((x^y^n)&1){
            int p,ps,gap=2*(m-1);
            int tt,res=0x3f3f3f3f,cnt=0;
            for(int op=0;op<2;++op){
                if(op){ps=1;p=x;}
                else{ps=m;p=m-x+1;}
                int tmp=(n-p)/gap;
                tt=tmp*2;p+=gap*tmp;
                while(p<n||ps!=y){
                    ++tt;
                    if(ps==1){
                        if(p+y-1>=n){p+=y-1;break;}
                        p+=m-1;ps=m;
                        continue;
                    }
                    if(ps==m){
                        if(p+m-y>=n){p+=m-y;break;}
                        p+=m-1;ps=1;
                        continue;
                    }
                }
                if(res>tt) res=tt,cnt=0;
                if(res==tt){
                    int d=(p-n)>>1;
                    cnt+=C(d+tt-1,d);
                    if(cnt>=P) cnt-=P;
                }
            }
            printf("%d %d\n",res+1,cnt);
        }
        else puts("0 0");
        return;
    }
}
int main(){
    n=read();m=read();q=read();lim=(m+1)<<1;
    for(int i=0;i<lim;++i) F.f[i]=G.f[i]=0;
    F.f[0]=G.f[0]=G.f[1]=G.f[lim-1]=1;
    fac[0]=1;
    for(int i=1;i<=m;++i) fac[i]=(ll)fac[i-1]*i%P;
    fiv[m]=qp(fac[m]);
    for(int i=m;i;--i) fiv[i-1]=(ll)fiv[i]*i%P;
    int ex=n-1;
    while(ex){
        if(ex&1) F=F*G;
        G=G*G;ex>>=1;
    }
    while(q--) solve();
    return 0;
}