自动搬运

查看原文

来自洛谷，原作者为

	yyyyxh OI 是啥 (O_o)？

搬运于2025-08-24 22:24:10，当前版本为作者最后更新于2024-01-12 20:42:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

• P：判一下是不是 $c_1=c_r$ 就行了。否则无解。

• R：同上。否则需要走两步，有两种走法。

• Q：注意到答案不超过 2 所以只有一些分讨，但比想象的情况多，比如你需要考虑 $n=m$ 的时候，Q 可以先走到某一个角落然后斜着一步走到。一种比较好的方法是直接做 $O(1)$ 条一次函数暴力分讨交点。

然后对于 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;
}