专栏文章

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

aaeiouaoeiu
CF2169D2题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min189sp
此快照首次捕获于
2025/12/01 18:54
3 个月前
此快照最后确认于
2025/12/01 18:54
3 个月前
查看原文
每次操作都将位置为 cc 的数移动到位置 f(c)=c−⌊cy⌋\displaystyle f(c)=c-\lfloor\frac cy\rfloor，注意到 f(x)f(x) 值唯一，可以考虑求出其反函数 g(x)g(x)，然后尝试计算 gx(k)g^x(k)（gxg^x 表示 g(g(…g(k)))g(g(\ldots g(k)))，其中 gg 有 xx 层）。
如何直观地推出 gg？考虑 c→f(c)c\to f(c) 的过程，将 [1,c][1,c] 划分为若干段，每一段长度为 yy，然后删去每一段的末尾（需要满足 y∤cy\nmid c，于是最后一段不足 yy，不作操作），此时 cc 移动到的位置即为 f(c)f(c)。反过来，可以看作 [1,f(c)][1,f(c)] 划分为若干个长为 y−1y-1 的段，每一段都在末尾加上一个点（最后一段除外），可以发现实际上加上了 ⌊f(c)−1y−1⌋\displaystyle \lfloor\frac{f(c)-1}{y-1}\rfloor 个点，于是我们得到 f(c)+⌊f(c)−1y−1⌋=c\displaystyle f(c)+\lfloor\frac{f(c)-1}{y-1}\rfloor=c，即 g(x)=x+⌊x−1y−1⌋\displaystyle g(x)=x+\lfloor\frac{x-1}{y-1}\rfloor。
接下来考虑如何求 gx(k)g^x(k)，注意到 ⌊x−1y−1⌋\displaystyle \lfloor\frac{x-1}{y-1}\rfloor 实际上有很多时候相同，可以考虑将这些相同的增量都压缩在一起。下面先证明这样做的复杂度是正确的：显然每次求出的增量都至少增加 11，则情况不弱于使得 ∑i=1ci≥x\displaystyle \sum_{i=1}^{c}i\ge x 的最小的 cc，而 c∼O(x)\displaystyle c\sim\mathcal{O}(\sqrt x)，于是至多需要求出 O(x)\displaystyle\mathcal{O}(\sqrt x) 次增量。
接下来计算增量的边界，设当前增量为 Δ=⌊k−1y−1⌋\displaystyle\Delta=\lfloor\frac{k-1}{y-1}\rfloor，则使得 ⌊k′−1y−1⌋=Δ\displaystyle\lfloor\frac{k'-1}{y-1}\rfloor=\Delta 的最大的 k′k' 为 (Δ+1)(y−1)(\Delta+1)(y-1)，于是跳 ⌊(Δ+1)(y−1)−kΔ⌋+1\displaystyle\lfloor\frac{(\Delta+1)(y-1)-k}{\Delta}\rfloor+1 次后会跳出边界。
时间复杂度 O(∑x)\displaystyle\mathcal{O}(\sum \sqrt x)。
codeCPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...