超级马——问题的放大与缩小

· · 题解

超级马

超级马

建议的前置知识

如果在阅读时感到困惑可以阅读这些链接中可能需要的前置知识。

群论简介 OI-WIKI：该链接下全部内容。

线性代数 OI-WIKI：该部分特征多项式部分前的全部内容。

小凯的疑惑：弄懂基于裴蜀定理的证明。

大体思路

两种主要的方向：图论和数学，图论做法的复杂度至少是 O(n^3T) 的，放弃考虑，考虑数学做法。

正整数集合的代数性质很差，不妨先考虑整数集合。

下面从两个角度来考量。

线性代数的角度

一个二维的线性空间只需要两个基就能生成，但这道题中的空间并非线性空间，整数集合仅仅是交换幺环，不是域，但我们同样可以从基的角度去考虑。

记 \operatorname{span}(u_1,u_2,\cdots u_n) 表示由这些向量通过线性变换生成的空间，注意到有 \operatorname{span}(u_1,u_2,\cdots u_n)=\operatorname{span}(u_1\pm u_2,u_2,\cdots u_n)，因为可以从 u_1\pm u_2 中减掉或者加上 u_2 得到原来的 u_1。

考虑对某一维运用辗转相减或者说辗转相除，最后该维只能有一个非零元素，而且这个非零元素必须为 \pm1。

对两维同时运用该算法即可判别是否可以在允许可逆操作的前提下到达。

多元一次方程的角度

达到任意点的条件等价于能够到达 (1,0),(-1,0),(0,1),(0,-1)，现在问题变成了解一个多元一次方程组：

p_1x_1 + p_2x_2 + p_nx_n=1 q_1x_1 + q_2x_2 + q_nx_n=0

求这个方程组的整数解也是困难的，我们不妨考虑将第二项作为限制，看第一项能得到什么。

在将第二项作为限制的前提下，记第一项能得到的数的集合为 S，那么方程组有解的一个充要条件是 \gcd(S)=1。考虑找到 S 的一个子集使得它的最大公约数为 1，我们考虑所有的无序对 i,j，令 x_k=0,k\neq i,k\neq j ，于是第一个方程的左边能生成 s_{i,j}=\dfrac{q_ip_j+q_jp_i}{\gcd(q_i,q_j)}，如果所有的 s 的 \gcd 为 1，那么原方程组显然有解，这是一个充分条件，事实上它也是必要的，证明可以参考文末的集训队论文。

将 p_i,q_i 视为向量 u_i，将方程组改成向量数乘的方程。

证明思路是证明如果存在整数解，那么一定将整体的求和拆分为若干个 u_iy_i+u_jy_j 的和，且满足 u_iy_i+u_jy_j=\begin{pmatrix}c\\0\end{pmatrix}，具体方式是归纳构造。

回归原问题

问题变成了已知在操作可逆的前提下能到达所有点，问是否存在一种方式使得在操作不可逆的前提下也能到达所有点。

如果所有的向量都落在同一个半平面内，那么显然不能到达所有点，否则，在每一条坐标轴的两个方向上都能找到一个点能够通过正向操作到达（两个向量只使用不涉及减法的的线性变换能得到的向量落在其小于 \pi 的夹角内且每一个有理点都能取到）。

于是 (p_i,q_i) 逆操作可以找到一个正整数 k 使得 (kp_i,kq_i) 能够在不用逆操作的前提下到达，然后进行 k-1 次 (p_i,q_i) 操作。

因此对所有坐标极角排序即可。

有一个 STL 函数叫 atan2(double x,double y)，能够在给定 x,y 坐标的情况下计算其极角，不用手写。

从方程组的角度看，可以改变一下 s_{i,j} 的定义，只让 q_iq_j\le 0 的两个向量贡献，如果 x 坐标依然同时能够取到正负，那么一定可以通过整数解构造得到非负整数解。注意，这并不代表我们构造 \gcd(s)=1 的时候不能使用 q_iq_j>0 的向量。

总结

问题的第一步是将问题 "放大" 到整数集合，以便更好的利用其生成空间的代数性质。

第二步是利用这些代数性质得到必要条件后再回到原问题考虑。

这样能够简化问题的核心原因是相比于原问题，我们解决问题的每一步都凭空多出了一些条件——第一部分我们可以更好的利用整数环下线性空间的性质，第二部分可以利用第一部分得到的必要条件。

凭空多出条件也是反证法和数学归纳法如此强大的原因。

代码

// 线性代数角度
#include <bits/stdc++.h>
using namespace std;
const int maxn=110;
const double pi=atan2(0,-1);
int n,i,x,y,T; double d;
struct vec{
    int x,y; double at;
    inline bool operator <(const vec &a)const{return at<a.at;}
}N[maxn],a,b,t;
int main(){
    scanf("%d",&T);
    st: while(T--){
        scanf("%d",&n);
        for(i=1;i<=n;++i){
            scanf("%d%d",&x,&y);
            N[i]={x,y,atan2(y,x)};
        }
        if(n<=2){printf("No\n");goto st;}
        sort(N+1,N+n+1); N[n+1]=N[1];
        for(i=1;i<=n;++i){
            if((d=N[i+1].at-N[i].at)<0) d+=2*pi;
            if(d>=pi){printf("No\n");goto st;}
        }
        for(a=N[1],i=2,y=0;i<=n;++i){
            b=N[i];
            while(b.x){
                t=a; a=b; x=t.x/b.x;
                b={t.x-x*b.x,t.y-x*b.y,0};
            } 
            y=__gcd(y,b.y);
        }
        if(abs(a.x)!=1||abs(y)!=1) printf("No\n");
        else printf("Yes\n");
    }
    return 0;
}

方程组角度

#include<bits/stdc++.h>
#define LL long long
using namespace std;
void read(int &x){
    x=0;char ch=getchar();int f=1;
    while((ch<'0'||ch>'9')&&ch!=45)ch=getchar();
    if(ch==45)ch=getchar(),f=-1;
    while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();
    x*=f;
}
template<typename T1,typename T2>void cmax(T1 &x,const T2 &y){if(y>x)x=y;}
template<typename T1,typename T2>void cmin(T1 &x,const T2 &y){if(y<x)x=y;}
const int N=3005;
int i,j,k,m,n,s,t;
int g[N][N],p[105],q[105],ap[105],aq[105];
int _gcd(int a,int b){
    return g[a][b]?g[a][b]:(!b?a:_gcd(b,a%b));
}
int fgcd(int a,int b){
    if(a<N&&b<N)return g[a][b];
    return !b||!a?max(a,b):fgcd(b,a%b);
}
bool check(){
    int f=0,pd[2]={};
    for(i=1;i<=n;i++){
        for(j=1;j<i;j++)if((p[i]||p[j])){
            int final;
            if(p[i]*p[j]>0)final=q[i]*ap[j]+q[j]*-ap[i];
            else final=q[i]*ap[j]+q[j]*ap[i],pd[0]|=final>0,pd[1]|=final<0;
            final/=fgcd(ap[i],ap[j]);
            f=fgcd(f,abs(final));
        }
        if(pd[0]&&pd[1]&&f==1)return 1;
    }
    return 0;
}
void _solve(){
    read(n);
    for(i=1;i<=n;i++)read(p[i]),read(q[i]),ap[i]=abs(p[i]),aq[i]=abs(q[i]);
    int f=1;
    f&=check();
    if(!f)return void(puts("No"));
    swap(p,q);swap(ap,aq);
    f&=check();
    puts(f?"Yes":"No");
}
signed main(){
    for(i=0;i<N;i++)for(j=0;j<=i;j++)g[i][j]=_gcd(i,j);
    for(i=0;i<N;i++)for(j=i;j<N;j++)g[i][j]=g[j][i];
    int T;read(T);
    while(T--){
        _solve();
    }
    return 0;
}

参考资料

IOI2004 国家集训队论文 《转化目标在解题中的应用》——栗师

Cry_For_theMoon 大佬的博客