题解：P13297 [GCJ 2013 #2] Multiplayer Pong

Nephrolepis · 2026-01-26 16:47:42 · 题解

简要思路：球的轨迹与球拍无关（竖边反弹只翻转 V_X，不改变 V_Y），因此双方的最优策略不改变落点序列。那么比赛是否结束以及何时结束，就完全由轮到的那名球员能否在两次自己出手之间赶到下一次落点决定。

~~大整数类讲的有点长了，高手不用看。~~

大整数的处理

考虑到这个数据范围（10^{100} 级别），所以首先搓一个大整数类 Z，基数 B=10^9，即每个 uint32_t 存储 9 位十进制数。

由于位数非常少，所以正常的高精乘法就可以，时间复杂度 \mathcal{O}(L^2)（FFT 是 \mathcal{O}(L\log L)，就算用迭代的实数 FFT，在这么小的数据范围下想超越朴素乘也基本不可能且没必要），高精除法也就顺理成章地用试商法（用不着高精乘），时间复杂度也是 \mathcal{O}(L^2)。

单精度乘除处理进位和余数，取模和 GCD 这些就不拿出来说了。

几个关键的点（设 V_X>0）

只需要检查同一名球员两次出手之间的位移是否可达：

因为每名球员初始位置可任意选择，所以每个人第一次出手一定能站在落点，所以之后只需检查两次自己出手间：
|y_\text{next}-y_\text{prev}|\le\text{paddleSpeed}\cdot\Delta t
同一侧同一名球员两次出手的时间间隔是常数：

球每次到同一侧竖边需要时间 \frac{2B}{V_X}。

LEFT 侧有 N 人轮换，因此同一名 LEFT 球员两次出手间隔：
\Delta t_L=\frac{2NB}{V_X}
RIGHT 同理：
\Delta t_R=\frac{2MB}{V_X}
消去分数，把纵坐标整体乘上 V_X，这样所有碰壁纵坐标都变成整数，判定式也变成整数比较。

令
P=2AV_X,\,H=AV_X
用展开 + 取模折叠来表示反弹：在模 P 下的值 r\in[0,\,P) 对应真实纵坐标（注意乘过 V_X）为：
y(r)=\min(r,\,P-r)
竖边碰撞序号为 k（从 1 开始），则得到：
r_k\equiv YV_X-XV_Y+V_YBk\pmod P
分别看两侧的碰撞序列：

RIGHT 侧是奇数 k，可以写成等差模序列的形式，步长 s=2V_YB；LEFT 侧是偶数 k，同样的步长 s，只是偏移不同。

所以可以注意到在模 P 的意义下两侧的落点序列都是：
r_n\equiv c+sn\pmod P\quad(n=1,\,2,\,\dots)
可以注意到某名球员下一次出手的落点只取决于一个固定平移 S：

LEFT：同一名球员相隔 N 次 LEFT 落点，所以：
r_{n+N}\equiv r_n+S_L\pmod P,\quad S_L\equiv sN\pmod P
允许的最大纵向位移（注意乘过 V_X）为：
D_L=V\cdot2NB
RIGHT：同理：
S_R\equiv sM\pmod P,\quad D_R=W\cdot2MB
因此对某侧来说，会导致失败的起始落点集合是（默认 r+s 在模 P 意义下）：
\mathcal{B}=\{r:|y(r+S)|-y(r)>D\}
注意到 \mathcal{B} 是常数个区间的并，因为 y(r)=\min(r,\,P-r) 是一条三角波，|y(r+S)-y(r)| 在 0,\,H,\,P-S,\,H-S 这些点之间是线性的，所以所谓的坏集合其实是 \mathcal{O}(1) 个整数区间。
如何在巨大的周期里找第一次落入坏区间的位置？

模等差序列的周期为 per=\frac{P}{\gcd(P,\,s)}。

所以考虑以下方法：

计数函数：前 n 项落入某个区间的次数。
二分：找到的最小前缀长度使计数 >0。

计数用经典的 floorsum 即可（$\sum{i=0}^{n-1}\left\lfloor\frac{ai+b}{m}\right\rfloor,来自 Atcoder 的 AC 库）（对这个感兴趣的可以看[这位大佬](https://www.cnblogs.com/RioTian/p/14584189.html)的详细论述）可在 \mathcal{O}(\log P) 内完成，整体 \mathcal{O}(\log^2 P)$。
得到两侧最早失败回合，比较全局先后：

LEFT 在其第 t_L 次到达左侧时失败，对应全局竖边碰撞序号 k_L=2t_L。

RIGHT 失败对应 k_R=2t_R。

较小者先发生，输出中的 z 就是失败方成功接球的次数 t-1。

Attention

注意到以上的简单论述及要点仅针对 V_X>0，其余情况简单扩展即可覆盖：

当 V_X=0：球永远碰不到竖直墙，DRAW。
当 V_X<0：把棋盘左右镜像并交换两队，可化成 V_X>0 的等价问题，最后输出时把 LEFT/RIGHT 再换回去即可。

Another attention

本篇题解以及代码给出的方法中采用的是类欧几里德计数（floor_sum）+ 二分查找这种组合策略，可以考虑使用纯欧几里德来代替这一部分，复杂度会更低，这里不详细讲，感兴趣的看官方题解去吧。

参考代码

#include<bits/stdc++.h>
using namespace std;
struct Z{
    static const uint32_t B=1000000000;
    vector<uint32_t>a;
    bool n;
    Z(long long v=0){
        *this=v;
    }
    Z& operator=(long long v){
        n=0;
        a.clear();
        if(v<0){
            n=1;
            v=-v;
        }
        while(v){
            a.push_back(v%B);
            v/=B;
        }
        return *this;
    }
    Z(const string&s){
        rd(s);
    }
    void rd(string s){
        n=0;
        a.clear();
        int p=0;
        if(!s.empty()&&s[0]=='-'){
            n=1;
            p=1;
        }
        for(int i=(int)s.size();i>p;i-=9){
            int l=max(p,i-9);
            uint32_t x=0;
            for(int j=l;j<i;j++) x=x*10+(s[j]-'0');
            a.push_back(x);
        }
        tr();
    }
    void tr(){
        while(!a.empty()&&a.back()==0)a.pop_back();
        if(a.empty())n=0;
    }
    bool z()const{
        return a.empty();
    }
    string str()const{
        if(a.empty()) return "0";
        string s=n?"-":"";
        s+=to_string(a.back());
        for(int i=(int)a.size()-2;i>=0;i--){
            string t=to_string(a[i]);
            s+=string(9-t.size(),'0')+t;
        }
        return s;
    }
};
static int ca(const Z&x,const Z&y){
    if(x.a.size()!=y.a.size()) return x.a.size()<y.a.size()?-1:1;
    for(int i=(int)x.a.size()-1;i>=0;i--) if(x.a[i]!=y.a[i]) return x.a[i]<y.a[i]?-1:1;
    return 0;
}
static bool operator<(const Z&x,const Z&y){
    if(x.n!=y.n) return x.n;
    int c=ca(x,y);
    return x.n?c>0:c<0;
}
static bool operator==(const Z&x,const Z&y){
    return x.n==y.n&&x.a==y.a;
}
static bool operator!=(const Z&x,const Z&y){
    return !(x==y);
}
static bool operator>(const Z&x,const Z&y){
    return y<x;
}
static bool operator<=(const Z&x,const Z&y){
    return !(y<x);
}
static bool operator>=(const Z&x,const Z&y){
    return !(x<y);
}
static Z abz(Z x){
    x.n=0;
    return x;
}
static void suba(Z&x,const Z&y){
    int64_t c=0;
    for(size_t i=0;i<x.a.size();i++){
        int64_t s=(int64_t)x.a[i]-(i<y.a.size()?y.a[i]:0)-c;
        if(s<0){
            s+=Z::B;
            c=1;
        }
        else c=0;
        x.a[i]=(uint32_t)s;
    }
    x.tr();
}
static Z& operator+=(Z&x,const Z&y){
    if(x.n==y.n){
        size_t n=max(x.a.size(),y.a.size());
        x.a.resize(n,0);
        uint64_t c=0;
        for(size_t i=0;i<n;i++){
            uint64_t s=c+x.a[i]+(i<y.a.size()?y.a[i]:0);
            x.a[i]=(uint32_t)(s%Z::B);
            c=s/Z::B;
        }
        if(c) x.a.push_back((uint32_t)c);
    }
    else{
        int c=ca(x,y);
        if(c==0){
            x=0;
            return x;
        }
        if(c>0) suba(x,y);
        else{
            Z t=y;
            suba(t,x);
            x=move(t);
        }
    }
    x.tr();
    return x;
}
static Z& operator-=(Z&x,const Z&y){
    Z t=y;
    if(!t.z()) t.n=!t.n;
    return x+=t;
}
static Z operator+(Z x,const Z&y){
    x+=y;
    return x;
}
static Z operator-(Z x,const Z&y){
    x-=y;
    return x;
}
static Z operator-(Z x){
    if(!x.z()) x.n=!x.n;
    return x;
}
static Z& operator*=(Z&x,uint32_t m){
    if(x.z()||m==0){
        x=0;
        return x;
    }
    uint64_t c=0;
    for(size_t i=0;i<x.a.size();i++){
        uint64_t cur=c+(uint64_t)x.a[i]*m;
        x.a[i]=(uint32_t)(cur%Z::B);
        c=cur/Z::B;
    }
    if(c) x.a.push_back((uint32_t)c);
    x.tr();
    return x;
}
static Z operator*(Z x,uint32_t m){
    x*=m;
    return x;
}
static Z operator*(const Z&x,const Z&y){
    if(x.z()||y.z()) return 0;
    Z r;
    r.n=x.n^y.n;
    r.a.assign(x.a.size()+y.a.size(),0);
    for(size_t i=0;i<x.a.size();i++){
        uint64_t c=0;
        for(size_t j=0;j<y.a.size()||c;j++){
            uint64_t cur=r.a[i+j]+c+(uint64_t)x.a[i]*(j<y.a.size()?y.a[j]:0);
            r.a[i+j]=(uint32_t)(cur%Z::B);
            c=cur/Z::B;
        }
    }
    r.tr();
    return r;
}
static Z& operator*=(Z&x,const Z&y){
    x=x*y;
    return x;
}
static Z& operator/=(Z&x,uint32_t v){
    if(x.z()) return x;
    uint64_t rem=0;
    for(int i=(int)x.a.size()-1;i>=0;i--){
        uint64_t cur=x.a[i]+rem*Z::B;
        x.a[i]=(uint32_t)(cur/v);
        rem=cur%v;
    }
    x.tr();
    return x;
}
static pair<Z,Z> dv(const Z&a,const Z&b){
    Z bb=abz(b),aa=abz(a);
    if(bb.z()) return {0,0};
    if(ca(aa,bb)<0) return {0,a};
    uint32_t norm=(uint32_t)(Z::B/((uint64_t)bb.a.back()+1));
    aa*=norm;
    bb*=norm;
    Z q;
    q.a.assign(aa.a.size(),0);
    q.n=a.n^b.n;
    Z r=0;
    for(int i=(int)aa.a.size()-1;i>=0;i--){
        r.a.insert(r.a.begin(),0);
        r.a[0]=aa.a[i];
        r.tr();
        uint64_t s1=r.a.size()<=bb.a.size()?0:r.a[bb.a.size()];
        uint64_t s2=r.a.size()<=bb.a.size()-1?0:r.a[bb.a.size()-1];
        uint64_t d=(s1*Z::B+s2)/bb.a.back();
        if(d>=Z::B) d=Z::B-1;
        Z t=bb*(uint32_t)d;
        r-=t;
        while(r.n){
            r+=bb;
            d--;
        }
        q.a[i]=(uint32_t)d;
    }
    q.tr();
    r.n=a.n;
    r/=norm;
    if(q.z()) q.n=0;
    if(r.z()) r.n=0;
    return {q,r};
}
static Z operator/(const Z&a,const Z&b){
    return dv(a,b).first;
}
static Z operator%(const Z&a,const Z&b){
    return dv(a,b).second;
}
static Z& operator/=(Z&a,const Z&b){
    a=a/b;
    return a;
}
static Z& operator%=(Z&a,const Z&b){
    a=a%b;
    return a;
}
static Z gd(Z a,Z b){
    a=abz(a);
    b=abz(b);
    while(!b.z()){
        Z r=a%b;
        a=b;
        b=r;
    }
    return a;
}
static Z mp(Z a,const Z&m){
    a%=m;
    if(a.n) a+=m;
    return a;
}
static Z fd(Z a,const Z&b){
    if(!a.n) return a/b;
    Z t=abz(a);
    t+=b-1;
    t/=b;
    if(!t.z()) t.n=1;
    return t;
}
static Z cd(Z a,const Z&b){
    if(!a.n){
        Z t=a;
        t+=b-1;
        return t/b;
    }
    Z t=abz(a);
    t/=b;
    if(!t.z()) t.n=1;
    return t;
}
static Z fs(Z n,Z m,Z a,Z b){
    if(n.z()) return 0;
    Z r=0;
    while(true){
        if(a>=m){
            auto qr=dv(a,m);
            Z t=(n-1)*n;
            t/=2;
            t*=qr.first;
            r+=t;
            a=qr.second;
        }
        if(b>=m){
            auto qr=dv(b,m);
            r+=n*qr.first;
            b=qr.second;
        }
        Z y=a*n+b;
        if(y<m) break;
        auto qr=dv(y,m);
        n=qr.first;
        b=qr.second;
        swap(m,a);
    }
    return r;
}
static Z clt(Z n,const Z&m,const Z&a,const Z&b,Z x){
    if(x<=0) return 0;
    if(x>=m) return n;
    Z add=m-x;
    Z f1=fs(n,m,b,a+add),f0=fs(n,m,b,a);
    return n-(f1-f0);
}
static Z cint(Z n,const Z&m,const Z&a,const Z&b,const Z&l,const Z&r){
    return clt(n,m,a,b,r+1)-clt(n,m,a,b,l);
}
static vector<pair<Z,Z>> bad(Z P,Z H,Z S,Z D){
    if(D>=H) return {};
    S=mp(S,P);
    if(S.z()) return {};
    Z bw=P-S;
    vector<Z> p={0,H,mp(P-S,P),mp(H-S,P)};
    sort(p.begin(),p.end());
    p.erase(unique(p.begin(),p.end()),p.end());
    vector<pair<Z,Z>> v;
    auto add=[&](Z l,Z r){
        if(l<=r)v.push_back({l,r});
    };
    for(size_t i=0;i<p.size();i++){
        Z L=p[i];
        Z R=i+1<p.size()?p[i+1]-1:P-1;
        if(L>R) continue;
        Z u=L;
        bool wr=u>=bw;
        Z c=wr?S-P:S;
        Z vv=u+c;
        bool s1=u<H,s2=vv<H;
        int a1=s1?1:-1,a2=s2?1:-1;
        Z b1=s1?0:P,b2=s2?0:P;
        int c1=a2-a1;
        Z c0=(a2==1?c:-c)+b2-b1;
        if(c1==0){
            if(abz(c0)>D) add(L,R);
        }
        else if(c1==2){
            Z l1=fd(D-c0,2)+1;
            add(max(L,l1),R);
            Z r2=cd(-D-c0,2)-1;
            add(L,min(R,r2));
        }
        else{
            Z r1=cd(c0-D,2)-1;
            add(L,min(R,r1));
            Z l2=fd(D+c0,2)+1;
            add(max(L,l2),R);
        }
    }
    sort(v.begin(),v.end());
    vector<pair<Z,Z>> m;
    for(auto &e:v){
        if(m.empty()||e.first>m.back().second+1) m.push_back(e);
        else if(e.second>m.back().second) m.back().second=e.second;
    }
    return m;
}
static Z fb(const Z&P,const Z&a,const Z&b,const vector<pair<Z,Z>>&iv){
    if(iv.empty()) return -1;
    Z g=gd(P,b),per=P/g,tot=0;
    for(auto &e:iv) tot+=cint(per,P,a,b,e.first,e.second);
    if(tot.z()) return -1;
    Z L=1,R=per;
    auto cnt=[&](const Z&n){
        Z s=0;
        for(auto &e:iv) s+=cint(n,P,a,b,e.first,e.second);
        return s;
    };
    while(L<R){
        Z mid=L+R;
        mid/=2;
        if(!cnt(mid).z()) R=mid;
        else L=mid+1;
    }
    return L-1;
}
static Z sol(const Z&P,const Z&H,const Z&s,const Z&c,const Z&n,const Z&sp,const Z&B){
    Z b=mp(s,P),a=mp(c+s,P);
    Z nm=n%P;
    Z S=(b*nm)%P;
    Z D=sp*2u*n*B;
    if(D>=H||S.z()) return -1;
    auto iv=bad(P,H,S,D);
    Z i=fb(P,a,b,iv);
    if(i.n) return -1;
    return i+1+n;
}
static Z rd(){
    string s;
    cin>>s;
    return Z(s);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    for(int tc=1;tc<=T;tc++){
        Z A=rd(),B=rd();
        Z N=rd(),M=rd();
        Z V=rd(),W=rd();
        Z Y=rd(),X=rd(),Vy=rd(),Vx=rd();
        bool sw=0;
        if(Vx.z()){
            cout<<"Case #"<<tc<<": DRAW\n";
            continue;
        }
        if(Vx.n){
            Vx=-Vx;
            X=B-X;
            swap(N,M);
            swap(V,W);
            sw=1;
        }
        if(Vy.n){
            Vy=-Vy;
            Y=A-Y;
        }
        Z P=A*2u*Vx,H=A*Vx;
        Z d=Vy*B,s=d*2u;
        Z a0=Y*Vx-Vy*X;
        Z tL=sol(P,H,s,a0,N,V,B);
        Z tR=sol(P,H,s,a0-d,M,W,B);
        int w=0;
        Z z=0;
        if(tL.n&&tR.n) w=0;
        else if(tL.n){
            w=1;
            z=tR-1;
        }
        else if(tR.n){
            w=2;
            z=tL-1;
        }
        else{
            Z kL=tL*2u,kR=tR*2u-1;
            if(kL<kR){
                w=2;
                z=tL-1;
            }
            else{
                w=1;
                z=tR-1;
            }
        }
        if(sw){
            if(w==1) w=2;
            else if(w==2) w=1;
        }
        cout<<"Case #"<<tc<<": ";
        if(w==0) cout<<"DRAW\n";
        else if(w==1) cout<<"LEFT "<<z.str()<<"\n";
        else cout<<"RIGHT "<<z.str()<<"\n";
    }
    return 0;
}

时间复杂度 \mathcal{O}(L^4)，空间复杂度 \mathcal{O}(L)，L 为数据位数。