「CEOI2020」象棋世界

下文默认 $n=R,m=C,x=c_1,y=c_R$

Pawn

略

Rook

略

Queen

先判掉一次到达的情况，然后就可以从起点和终点分别画出5条可行线

由此得到若干交点，手动数一下有几个交点在内部的整点上

void QQQ(){
	int d=abs(x-y);
	if(d==n-1 || d==0) puts("1 1"); // 一次到达
	else {
		d=(n-1-d)/2;
		int res=4;
		if(n==m) {
            // 一条斜着，一条平着
			if(x==1 || x==n) res++;
			if(y==1 || y==n) res++;
		}
		if(((x+1)&1)==((y+n)&1)) { // 先判断整点，然后判断两条斜线相交是否在内部
			if(min(x,y)-d>=1) res++;
			if(max(x,y)+d<=m) res++;
		}
		printf("%d %d\n",2,res);
	}
}

$\$

Bishop

看起来是很复杂的问题，但是实际上可以从一个简单的贪心入手

判定条件

可以发现，任意一次行走的直线上，坐标 $(x,y)$ 的 $(x+y)\mod 2$ 不变

所以只要 $x+1\equiv y+n\pmod 2$ 即可

贪心策略

首先一定是每次向前走

第一步选择向左/右，然后每次转向，每次走都顶到边界线

但是这样显然会无法到达最终位置

纠正方法

考虑贪心到达的最后位置为 $to$ ，那么得到的差值 $|to-y|$ 是我们要矫正的距离

而矫正方法：在中途出现的每次转向位置，向里面”凹”进去一点，每凹进去一格，实际上相当于少走了两格

注意矫正的方向是根据最后一步走的方向而变化的，因此如果矫正方向不对，需要额外增加一步

此时，相当于需要多矫正到沿边界线对称的位置，需要多走 $2(to-1)$ 或者 $2(m-to)$ 的距离

假设走了 $c$ 步，那么我们有 $c-1$ 个转折点，最后将这若干的矫正距离分配到 $c-1$ 个转折点上，可以用一个组合数解决

由于矫正距离是 $O(m)$ 的，所以组合数显然可以在 $O(m)$ 时间内求出

$\$

最后将向左向右合并即可

ll qpow(ll x,ll k=P-2) {
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}
int C(int n,int m) {
	if(m>n-m) m=n-m;
	int a=1,b=1;
	rep(i,1,m) a=1ll*a*(n-i+1)%P,b=1ll*b*i%P;
	return a*qpow(b)%P;
}
int Divide(int n,int m){ // Divide n elements in to m groups , each can be empty
	if(m<=0 && n>0) return 0;
	return C(n+m-1,m-1);
}
void BBB(){
	if(((x+1)&1)!=((y+n)&1)) return puts("0 0"),void();
	auto Subsolver=[&](int x,int y){
        // assume that we go left first
		int c=0,to=x,dis=n-1; // count , towardsposition
		c=1,dis-=x-1,to=1; // go left by x-1
		c+=dis/(m-1),to=((dis/(m-1))&1)?m:1,dis%=m-1; // then each step m-1 opposite
		if(dis) c++,to=to==1?to+dis:to-dis; // reach destination (NO!)
		if(to==y) return mp(c,1);
		int d=abs(to-y)/2;
		if((c&1)  && y>to) d+=to-1,c++;
		if((~c&1) && y<to) d+=m-to,c++;
		return mp(c,Divide(d,c-1));
	};
	Pii l=Subsolver(x,y),r=Subsolver(m-x+1,m-y+1);
	if(l.first>r.first) swap(l,r);
	if(r.first==l.first) (l.second+=r.second)%=P;
	printf("%d %d\n",l.first,l.second);
}

$\$

King

可以发现，每次一定是向前的三个方向走，由此可以得到一个简单的 $O(nm)\$ $dp$

用矩阵优化可以做到 $O(m^3\log n)$ 求出所有的答案

难点在于如果快速求出这个矩阵 $A$ 的 $A^{n-1}$ ，即要加速矩阵求幂

容易想到用 特征多项式 解决该问题，参考

问题分为两步

得到 $p_m(\lambda)$

列出我们的转移矩阵 $A=$

$\begin{matrix}1\ 1\ 0\ 0\ 0\ 0\ \cdots \ 0\\ 1\ 1\ 1\ 0\ 0\ 0\ \cdots \ 0\\ 0\ 1\ 1\ 1\ 0\ 0\ \cdots \ 0\\ \cdots\cdots\cdots\cdots \\ 0\ \cdots\ 0\ 0\ 1\ 1\ 1\ 0\\0\ \cdots\ 0\ 0\ 0\ 1\ 1\ 1\\ 0\ \cdots\ 0\ 0\ 0\ 0\ 1 \ 1\end{matrix}$

$\lambda I-A=$

$\lambda -1$	$-1$	$0$	$0$	$0$	$0$	$\cdots$	$0$
$-1$	$\lambda -1$	$-1$	$0$	$0$	$0$	$\cdots$	$0$
$0$	$-1$	$\lambda -1$	$-1$	$0$	$0$	$\cdots$	$0$
$\cdots$	$\cdots$	$\cdots$	$\cdots$	$\cdots$	$\cdots$	$\cdots$	$\cdots$
$0$	$0$	$\cdots$	$0$	$-1$	$\lambda -1$	$-1$	$0$
$0$	$0$	$\cdots$	$0$	$0$	$-1$	$\lambda -1$	$-1$
$0$	$0$	$\cdots$	$0$	$0$	$0$	$-1$	$\lambda -1$

每一行有 $2/3$ 个元素，看起来并不是很好得到行列式

但是容易得到一个递推式，设 $m$ 阶转移矩阵的特征多项式为 $p_m(\lambda)$

如果最后一行取第 $m$ 个元素，值为 $(\lambda-1)p_{m-1}(\lambda)$

如果最后一行取第 $m-1$ 个元素，值为 $-p_{m-2}(\lambda)$

因而得到

p_{m} (λ) = {\begin{aligned} 1 & m = 0 \\ λ - 1 & m = 1 \\ (λ - 1) p_{m - 1} (λ) - p_{m - 2} (λ) & m > 1 \end{aligned}

$p_m(\lambda)=\left\{\begin{aligned}1&& m=0\\ \lambda-1 && m=1\\ (\lambda-1)p_{m-1}(\lambda)-p_{m-2}(\lambda) && m>1\end{aligned}\right.$

可以在 $O(m^2)$ 的时间内暴力求出，也可以得到通项公式(太憨了)

那么得到关系用 $\lambda^n\mod p_m(\lambda)$ 的系数优化计算，可以用暴力实现的多项式取模+快速幂得到 $O(m^2\log n)$

当然也可以优化

$\$

求出 $A^0,A^1,A^2\cdots A^m$

直接求显然是 $O(m^3)$ 的，~~卡一卡说不定能过？~~

由于走的是一个 $m\times m$ 的棋盘，可以用一个简单容斥得到答案

设 $f_{x,y}$ 为从 $x$ 走到 $y$ ，中途允许超出边界的方案数

由于棋盘只有 $m\times m$ ，中途最多只会可能经过一条边界线

而一旦在某一个时刻超出边界线到达 $0/m+1$ ，那么接下来达到这条边界线两侧对称点的方案数是一样的

即：跨过了某一条边界线 $0/m+1$ 的不合法方案数，可以用到达 $y$ 关于这条边界线的 对称点的 不一定合法方案数得到

而不一定合法的 $f_{x,y}$ 实际上只和 $|x-y|$ 有关

由此，可以用 $f_{0,i}$ 表示出 $A^i_{x,y}$ ，那么接下来只需要先计算出 $f_{0,i}$ 对于系数的求和，最终进行一次容斥，减去两侧不合法方案数即可

typedef vector <int> Poly;
Poly operator * (const Poly &a,const Poly &b){
	int n=a.size()-1,m=b.size()-1;
	Poly c(n+m+1);
	rep(i,0,n) rep(j,0,m) c[i+j]=(c[i+j]+1ll*a[i]*b[j])%P;
	return c;
}
Poly operator * (Poly a,const int &b){
	for(int &i:a) i=1ll*i*b%P;
	return a;
}
Poly operator + (Poly a,const Poly &b){
	if(a.size()<b.size()) a.resize(b.size());
	rep(i,0,b.size()-1) a[i]+=b[i],Mod1(a[i]);
	return a;
}
Poly operator - (Poly a,const Poly &b){
	if(a.size()<b.size()) a.resize(b.size());
	rep(i,0,b.size()-1) a[i]-=b[i],Mod2(a[i]);
	return a;
}
Poly operator % (Poly a,const Poly &b){
	int n=a.size()-1,m=b.size()-1;
	if(n<m) return a;
	assert(b[m]==1);
	drep(i,n-m,0) rep(j,0,m) a[i+j]=(a[i+j]+1ll*(P-a[i+m])*b[j])%P;
	a.resize(m);
	return a;
}
Poly Pow(Poly x,int k,Poly Mod){
	Poly res=x; k--;
	for(;k;k>>=1,x=x*x%Mod) if(k&1) res=res*x%Mod;
	return res;
}

Poly F,G,T=Poly{P-1,1};
int f[N*2],g[N*2],H[N*2];
void KKKInit(){
	G=Poly{1},F=T;
	rep(i,2,m) swap(F,G),F=G*T-F; // 递推特征多项式
	F=Pow(Poly{0,1},n-1,F); // 求出x^{n-1} mod p(x)
	f[0]=1,H[0]=F[0];
	rep(t,1,F.size()-1) { // 求出f_{0,i}，只需要求一半
		rep(i,0,t) g[i]=f[i];
		rep(i,0,t) {
			f[i]=(0ll+(i?g[i-1]:g[1])+g[i]+g[i+1])%P;
			H[i]=(H[i]+1ll*f[i]*F[t])%P; // 乘上系数累和
		}
	}
}
void KKK(){
	int res=H[abs(x-y)];
    // 两侧对称点
	// y -> 0-(y-0)=-y
	// y -> m+1+(m+1-y)=2(m+1)-y
	res-=H[abs(-y-x)];
	res-=H[abs(2*(m+1)-y-x)];
    // 容斥
	res=(res%P+P)%P;
	printf("%d %d\n",n-1,res);
}

orangejuice's blog

按ctrl会跳搜索，右上角选择day/night mode 似乎修好了搜索