「CEOI2020」象棋世界 下文默认n = R , m = C , x = c 1 , y = c R n = R , m = C , x = c 1 , y = c R
Pawn 略
Rook 略
Queen 先判掉一次到达的情况,然后就可以从起点和终点分别画出5条可行线
由此得到若干交点,手动数一下有几个交点在内部的整点上
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 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 ) 的( x + y ) mod 2 ( x + y ) mod 2 不变
所以只要x + 1 ≡ y + n ( mod 2 ) x + 1 ≡ y + n ( mod 2 ) 即可
贪心策略 首先一定是每次向前走
第一步选择向左/右,然后每次转向,每次走都顶到边界线
但是这样显然会无法到达最终位置
纠正方法 考虑贪心到达的最后位置为t o t o ,那么得到的差值| t o − y | | t o − y | 是我们要矫正的距离
而矫正方法:在中途出现的每次转向位置,向里面”凹”进去一点,每凹进去一格,实际上相当于少走了两格
注意矫正的方向是根据最后一步走的方向而变化的,因此如果矫正方向不对,需要额外增加一步
此时,相当于需要多矫正到沿边界线对称的位置,需要多走2 ( t o − 1 ) 2 ( t o − 1 ) 或者2 ( m − t o ) 2 ( m − t o ) 的距离
假设走了c c 步,那么我们有c − 1 c − 1 个转折点,最后将这若干的矫正距离分配到c − 1 c − 1 个转折点上,可以用一个组合数解决
由于矫正距离是O ( m ) O ( m ) 的,所以组合数显然可以在O ( m ) O ( m ) 时间内求出
最后将向左向右合并即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 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) { 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){ int c=0 ,to=x,dis=n-1 ; c=1 ,dis-=x-1 ,to=1 ; c+=dis/(m-1 ),to=((dis/(m-1 ))&1 )?m:1 ,dis%=m-1 ; if (dis) c++,to=to==1 ?to+dis:to-dis; 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 ( n m ) O ( n m ) d p d p
用矩阵优化可以做到O ( m 3 log n ) O ( m 3 log n ) 求出所有的答案
难点在于如果快速求出这个矩阵A A 的A n − 1 A n − 1 ,即要加速矩阵求幂
容易想到用 特征多项式 解决该问题,参考
问题分为两步
得到p m ( λ ) p m ( λ ) 列出我们的转移矩阵A = A =
1 1 0 0 0 0 ⋯ 0 1 1 1 0 0 0 ⋯ 0 0 1 1 1 0 0 ⋯ 0 ⋯ ⋯ ⋯ ⋯ 0 ⋯ 0 0 1 1 1 0 0 ⋯ 0 0 0 1 1 1 0 ⋯ 0 0 0 0 1 1 1 1 0 0 0 0 ⋯ 0 1 1 1 0 0 0 ⋯ 0 0 1 1 1 0 0 ⋯ 0 ⋯ ⋯ ⋯ ⋯ 0 ⋯ 0 0 1 1 1 0 0 ⋯ 0 0 0 1 1 1 0 ⋯ 0 0 0 0 1 1
λ I − A = λ I − A =
λ − 1 λ − 1
− 1 − 1
0 0
0 0
0 0
0 0
⋯ ⋯
0 0
− 1 − 1
λ − 1 λ − 1
− 1 − 1
0 0
0 0
0 0
⋯ ⋯
0 0
0 0
− 1 − 1
λ − 1 λ − 1
− 1 − 1
0 0
0 0
⋯ ⋯
0 0
⋯ ⋯
⋯ ⋯
⋯ ⋯
⋯ ⋯
⋯ ⋯
⋯ ⋯
⋯ ⋯
⋯ ⋯
0 0
0 0
⋯ ⋯
0 0
− 1 − 1
λ − 1 λ − 1
− 1 − 1
0 0
0 0
0 0
⋯ ⋯
0 0
0 0
− 1 − 1
λ − 1 λ − 1
− 1 − 1
0 0
0 0
⋯ ⋯
0 0
0 0
0 0
− 1 − 1
λ − 1 λ − 1
每一行有2 / 3 2 / 3 个元素,看起来并不是很好得到行列式
但是容易得到一个递推式,设m m 阶转移矩阵的特征多项式为p m ( λ ) p m ( λ )
如果最后一行取第m m 个元素,值为( λ − 1 ) p m − 1 ( λ ) ( λ − 1 ) p m − 1 ( λ )
如果最后一行取第m − 1 m − 1 个元素,值为− p m − 2 ( λ ) − p m − 2 ( λ )
因而得到
p m ( λ ) = ⎧ ⎨ ⎩ 1 m = 0 λ − 1 m = 1 ( λ − 1 ) p m − 1 ( λ ) − p m − 2 ( λ ) m > 1 p m ( λ ) = { 1 m = 0 λ − 1 m = 1 ( λ − 1 ) p m − 1 ( λ ) − p m − 2 ( λ ) m > 1
可以在O ( m 2 ) O ( m 2 ) 的时间内暴力求出,也可以得到通项公式(太憨了)
那么得到关系用λ n mod p m ( λ ) λ n mod p m ( λ ) 的系数优化计算,可以用暴力实现的多项式取模+快速幂得到O ( m 2 log n ) O ( m 2 log n )
当然也可以优化
求出A 0 , A 1 , A 2 ⋯ A m A 0 , A 1 , A 2 ⋯ A m 直接求显然是O ( m 3 ) O ( m 3 ) 的,卡一卡说不定能过?
由于走的是一个m × m m × m 的棋盘,可以用一个简单容斥得到答案
设f x , y f x , y 为从x x 走到y y ,中途允许超出边界的方案数
由于棋盘只有m × m m × m ,中途最多只会可能经过一条边界线
而一旦在某一个时刻超出边界线到达0 / m + 1 0 / m + 1 ,那么接下来达到这条边界线两侧对称点的方案数是一样的
即:跨过了某一条边界线0 / m + 1 0 / m + 1 的不合法方案数,可以用到达y y 关于这条边界线的 对称点的 不一定合法方案数得到
而不一定合法的f x , y f x , y 实际上只和| x − y | | x − y | 有关
由此,可以用f 0 , i f 0 , i 表示出A i x , y A x , y i ,那么接下来只需要先计算出f 0 , i f 0 , i 对于系数的求和,最终进行一次容斥,减去两侧不合法方案数即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 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); f[0 ]=1 ,H[0 ]=F[0 ]; rep (t,1 ,F.size ()-1 ) { 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)]; 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); }