[CF2169D2] Removal of a Sequence (Hard Version) 题解

aeiouaoeiu · 2025-11-24 21:05:12 · 题解

每次操作都将位置为 c 的数移动到位置 \displaystyle f(c)=c-\lfloor\frac cy\rfloor，注意到 f(x) 值唯一，可以考虑求出其反函数 g(x)，然后尝试计算 g^x(k)（g^x 表示 g(g(\ldots g(k)))，其中 g 有 x 层）。

如何直观地推出 g？考虑 c\to f(c) 的过程，将 [1,c] 划分为若干段，每一段长度为 y，然后删去每一段的末尾（需要满足 y\nmid c，于是最后一段不足 y，不作操作），此时 c 移动到的位置即为 f(c)。反过来，可以看作 [1,f(c)] 划分为若干个长为 y-1 的段，每一段都在末尾加上一个点（最后一段除外），可以发现实际上加上了 \displaystyle \lfloor\frac{f(c)-1}{y-1}\rfloor 个点，于是我们得到 \displaystyle f(c)+\lfloor\frac{f(c)-1}{y-1}\rfloor=c，即 \displaystyle g(x)=x+\lfloor\frac{x-1}{y-1}\rfloor。

接下来考虑如何求 g^x(k)，注意到 \displaystyle \lfloor\frac{x-1}{y-1}\rfloor 实际上有很多时候相同，可以考虑将这些相同的增量都压缩在一起。下面先证明这样做的复杂度是正确的：显然每次求出的增量都至少增加 1，则情况不弱于使得 \displaystyle \sum_{i=1}^{c}i\ge x 的最小的 c，而 \displaystyle c\sim\mathcal{O}(\sqrt x)，于是至多需要求出 \displaystyle\mathcal{O}(\sqrt x) 次增量。

接下来计算增量的边界，设当前增量为 \displaystyle\Delta=\lfloor\frac{k-1}{y-1}\rfloor，则使得 \displaystyle\lfloor\frac{k'-1}{y-1}\rfloor=\Delta 的最大的 k' 为 (\Delta+1)(y-1)，于是跳 \displaystyle\lfloor\frac{(\Delta+1)(y-1)-k}{\Delta}\rfloor+1 次后会跳出边界。

时间复杂度 \displaystyle\mathcal{O}(\sum \sqrt x)。

::::info[code]

#include<bits/stdc++.h>
#define pb emplace_back
#define pob pop_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const ll maxn=507,ee=1e18,p=998244353;
ll x,y,k;
ll solve(void){
    ll cur=k,stp,tot=0,val;
    if(k<y) return k;
    if(y==1) return -1;
    for(;;){
        val=(cur-1)/(y-1);
        stp=min(x-tot,((val+1)*(y-1)-cur)/val+1);
        cur+=val*stp,tot+=stp;
        if(cur>1e12) return -1;
        if(tot==x) break;
    }
    return cur;
}
int main(void){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll T=1; cin>>T;
    for(;T--;){
        cin>>x>>y>>k;
        cout<<solve()<<"\n";
    }
    return 0;
}

::::