【学习笔记】2018icpc沉阳K题

这道题解大概是去年10月队训后写的。之前它存储在本地，没有发布到博客上。昨天吃饭的时候大概和朋友聊到了这个问题，他随口说了几句让我发给他(x)，于是这个博客就诞生了

K.让火焰开始

问题含义

约瑟夫的问题，\(n\)人，数到\(k\)出去，问\(m\)最初的人的位置保证为 \(min\{m,k\}\leq 10^6\)

怎么做

呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜

开始处理之前，将数字更改为\(0,1,2,...,n-1\)这样更容易做到(

• \(f(n,m)=[f(n-1,m-1)+k] \%n\)
• \(f(n,m)\) 代表报告该人号码\(m\) 的第 \(n\) 个人的号码谁出去了
• 转接给\(n-1\)人，对应外出的\(m-1\)人，并继续从他处汇报\ (k\)，对应\(m\)的编号
• 模 \(n\)
• 边界条件\(f(n,1)=(k-1)\%n\)

据此我可以直接想到\(m\)小情况\(O(m)\)暴力

那么\(k\leq m\) 的情况又如何呢？

• \(k\)小，\(n\)大(\(m\leq n\))表示距离很小如果跳一次，需要取模的情况就会减少！
  也就是说，我们从 \(n-m+1\) \%n 考虑公式 \(n,m)=[f(n-1,m-1)+k] \)，直观分析，需要跳很多步才会遇到需要取模的情况。

• 而我们只需要计算\(t\)可以在连续跳跃而不需要触发模的最大步数\(t\)，然后连续跳跃 \(t+1\) 步骤，然后对相应的 \(n'\) 取模。这个过程可以在 \(O(1)\)

  中实现

代码

#include
使用命名空间 std；
#定义rep(i,a,b) for(register ll i=(a);i<=(b);i++)
typedef 长长 ll；
内联 ll 求解(ll n,ll m,ll k)
{
if(k==1)返回m-1；
如果(m<=k)
{
ll res=(k-1)%(n-m+1);
代表(i,n-m+2,n)res=(res+k)%i;
返回资源；
}
lllen=n-m+1；
ll res=(k-1)%(n-m+1);
米——；

当(米>0)
{
ll t=(len-res)/(k-1);
如果(m<=t)
{
分辨率=(分辨率+m*k)%(len+m);
m=0;
}别的
{
res=(res+t*k)%(len+t);
res=(res+k)%(len+t+1);
m-=t+1；
len+=t+1；
}
}
返回资源；
}

int main()
{
int T;scanf("%d",&T);
n，m，k；
代表(t,1,T)
{
scanf("%lld%lld%lld",&n,&m,&k);
printf("情况 #%lld: %lld\n",t,solve(n,m,k)+1);
}
返回0；
}

核心代码是

ll len=n-m+1;
ll res=(k-1)%(n-m+1);
米——；
而（m>0）{
    ll t=(len-res)/(k-1);
    如果（m<=t）{
        分辨率=(分辨率+m*k)%(len+m);m=0；
    }别的{
        res=(res+t*k)%(len+t);
        res=(res+k)%(len+t+1);
        m-=t+1；
        len+=t+1；
    }
}

这一段。

用\(len\)表示当前\(n'\)，res记录答案，并使用递归公式从小到大推回

计算每次可跳跃的最大步数\(t\)请与\(m\)

*复杂性分析

（这部分证明来自@Mobius喵x）

• 考虑将 \(y\) 记录为当前 \(n'\)，并将 \(x\) 记录为当前的数量迭代。
• 对于 \(y\)，我们可以将其估计为 \(y=tk\)，同时注意到 \(\begin{aligned}\frac{ dy}{dx}=\frac{tk-k}{k}=t-1\end{aligned}\)这样的近似关系
• 得到方程 \(\begin{aligned}\frac{dy}{dx}-\frac{y}{k}=-1\end{aligned}\)
• 这个方程很容易解。最后，将问题中的\(y\)替换为n，得到\(x=kln(n-k)-Ck\),
• 所以整个算法的时间复杂度非常优秀\(O(klog(n))\)