CF1993F2 题解

· · 题解

Problem Link

题目大意

给定 w\times h 矩形网格，以及一条长度为 q 的操作序列，一个点从 (0,0) 开始按操作序列向上下左右运动，当一个点超出左右边界，就翻转操作序列中的左右操作，当一个点超出上下边界，就翻转操作序列中的上下操作。

查询执行 k 次操作序列后会经过多少次原点。

数据范围：n\le 10^6。

思路分析

如果遇到边界后不翻转操作，那么这个点会在无穷大网格上运动，划分成若干 w\times h 的矩形区域。

如果这个点当前位置和起点左右间隔奇数个区域，那么当前经过奇数条左右边界，同理如果这个点当前位置和终点上下间隔奇数个区域，那么当前经过奇数条上下边界。

因此每个点都唯一对应原始 w\times h 区域的一个点，即左右间隔奇数个区域时左右对称，上下间隔奇数个区域时上下对称。

那么对应 (0,0) 的点就是所有 (x,y) 满足 2w \mid x,2h \mid y 的点。

因此枚举操作序列的位置，相当于求有多少个 i<k 满足 sx+i\times dx\equiv 0\pmod{2w},sy+i\times dy\equiv 0\pmod{2h}，先简化直接关于 i 的方程，然后 exgcd 求最小解和周期，即可计算 i 的个数。

时间复杂度 \mathcal O(n)。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll exgcd(ll a,ll b,ll &x,ll &y) {
    if(!b) return x=1,y=0,a;
    ll g=exgcd(b,a%b,y,x);
    return y-=a/b*x,g;
}
ll inv(ll a,ll p) {
    ll x,y; exgcd(a,p,x,y);
    return (x%p+p)%p;
}
const int MAXN=1e6+5;
int px[MAXN],py[MAXN];
char str[MAXN];
void solve() {
    ll _,k,n,m,ans=0;
    cin>>_>>k>>m>>n>>(str+1),n*=2,m*=2;
    for(int i=1;i<=_;++i) {
        px[i]=(px[i-1]+(str[i]=='D'?n-1:str[i]=='U'))%n;
        py[i]=(py[i-1]+(str[i]=='L'?m-1:str[i]=='R'))%m;
    }
    ll dx=px[_],dy=py[_],gx=__gcd(dx,n),gy=__gcd(dy,m);
    ll p=n/gx,q=m/gy,ix=inv(dx/=gx,p),iy=inv(dy/=gy,q);
    ll u,v,d=exgcd(p,q,u,v),e=p/d*q;
    for(int i=1;i<=_;++i) {
        ll rx=(n-px[i])%n,ry=(m-py[i])%m;
        if(rx%gx||ry%gy) continue;
        rx=rx/gx*ix%p,ry=ry/gy*iy%q;
        //k mod p = rx, k mod q = ry
        if((ry-rx)%d) continue;
        ll z=q/d,s=((ry-rx)/d*u%z+z)%z,k0=s*p+rx;
        if(k0<k) ans+=(k-k0-1)/e+1;
    }
    cout<<ans<<"\n";
}
signed main() {
    ios::sync_with_stdio(false);
    int T; cin>>T;
    while(T--) solve();
    return 0;
}