[ICPC 2018 Shenyang Onsite K][Gym 101955K]Let the Flames Begin

Link

Solution

求步长为k的约瑟夫游戏中第m个出圈的人。
n\le 10^{18},\min{m,k}\le 10^6

The Initial Josephus Problem Solution

f[n]表示n个人围成一圈玩约瑟夫最后剩下的人的标号。
由于删掉一个人之后就会变成n-1的问题,只需要考虑删掉这一个人对于n-1问题的影响。可以发现,删掉第k个人的影响只是n-1问题中的第一个人变成大问题中的第k+1个人,也就是所有人的标号都增加了k
因此f[n]=(k+f[n-1])\mod n(从0开始标号)

This Enhanced Problem Solution

类似的思路
f[n][m]表示n个人第m个出圈的是谁,那么根据前面的分析f[n][m]=(k+f[n-1][m-1])\mod n
边界条件f[n][1]=m-1,在m小的时候直接递推过去就行了。
km大的时候,核心思想是优化递推式。由于kn大,所以走很多步才会被膜一次,那么就算一下会走几步被膜,把k乘上次数去算,一次走多步。
假设当前递推值为p,当前总人数为tx步之后需要mod,则有下式
p+xk\ge t+x。根据此式就能解出x了。

Code

int main() {
    int T;fin>>T;
    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d: ",ks);
        long long n,m,k;fin>>n>>m>>k;
        long long Ans=(k-1)%(n-m+1);
        if(m<k) {
            for(int i=2;i<=m;++i)
                Ans=(Ans+k)%(n-m+i);
            ++Ans;
        } else {
            if(k==1)
                Ans=m;
            else {
                long long tot,p,x;
                for(tot=n-m+1,p=(k-1)%(n-m+1);
                        tot+(x=(tot-p)/(k-1)+((tot-p)%(k-1)!=0))<=n;
                        (p+=k*x)%=(tot+=x));
                p+=(n-tot)*k;
                Ans=++p;
            }
        }
        fout<<Ans<<'\n';
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注