嘟嘟噜 题解【约瑟夫环】【递归】

作者: wjyyy 分类: 约瑟夫环,解题报告,递归 发布时间: 2018-10-19 16:13

点击量:19

 

    约瑟夫环的加速处理。

Description

由于众所周知的原因, 冈部一直欠真由理一串香蕉.

为了封上真由理的嘴, 冈部承诺只要真由理回答出这个问题, 就给她买一车的香蕉:

一开始有\(n\)个人围成一个圈, 从\(1\)开始顺时针报数, 报出\(m\)的人被机关处决. 然后下一个人再从\(1\)开始报数, 直到只剩下一个人.

红莉栖: “这不就是约瑟夫问题吗…”

伦太郎: “助手你给我闭嘴!”

真由理虽然已经晕头转向了, 但听到有一车的香蕉, 两眼便放出了光芒.

那个呢, 真由氏很想要一车子的香蕉呢. 如果可以帮帮我的话, 我可以把一些香蕉分给你哟, 诶嘿嘿. 拜托你啦.”

Input Format

第一行一个整数\(T\) , 表示数据组数.

接下来\(T\)行, 每行两个整数 \(n, m\).

Output Format

对于每组数据, 输出一行一个整数, 表示幸存者的编号.

Sample

Input

5
4 6
2 8
2 9
8 8
7 9

Output

3 1 2 
4 7

Constraints

测试点编号 \(n\) \(m\)
\(1\) \(\le 10^5\) \(\le 10^5\)
\(2\) \(\le 10^6\) \(\le 10^5\)
\(3\) \(\le 10^9\) \(\le 2\)
\(4\)
\(5\) \(\le 3\)
\(6\)
\(7\) \(\le 10^3\)
\(8\) \(\le 10^4\)
\(9\) \(\le 10^5\)
\(10\)

对于\(100\%\)的数据,\(1\le T\le 20,1\le n\le 10^9,1\le m\le 10^5\).

题解:

    题目就是要求\(n\le 10^9,m\le 10^5\)范围内的约瑟夫问题的解。因为之前没有做过这样的问题,只是从高一的OI招新考试(2333)中听说了这个东西,所以不知道有什么结论……

 

    花了二十分钟打了个表,找了很久的规律……

    本来以为横着会有循环节,这样稍微处理一下就是\(O(Tm)\)的了,但是多打了一些并没有……此时看了一下纵向貌似有一些规律,也看到了循环节,但是规律都不明显。然后我看到了形如第5列的”3,8,3,8“,貌似是\(d=5\)的等差?理智告诉我再去检查几个,发现都有这样的规律,但是也有很多不满足的。既然是纵向的,那么\(n\),也就是人的总数会改变,那么上界就是会变的,考虑每次对\(n\)取膜……

 

    然后就把第5列拎出来了w:

 

    验证了这样的规律,这\(O(n)\)就实锤了。递推公式就是\(f_i\equiv f_{i-1}+m\bmod i\),若\(f_i=0\),则该轮最后留下来的编号是\(i\)。这就是著名约瑟夫问题的递推解法。但是让我把表给打出来了

 

    这个问题就是:大小为\(n\)的约瑟夫环出圈一个人,子问题就转化为了新的大小为\(n-1\)的约瑟夫环出圈后结果。递推开始位置与上一次出圈的位置有关。

 

    这里的递推主要影响因素就是取模,然后考虑\(m\)是固定的,因此当\(i\)很大时,加很多次\(m\)都不会涉及到\(i\)。那么我们可以加速,直接递推\(i\)到下一个取模的地方,甚至到后来\(i\)达到\(10^9\)数量级,\(m\)是\(10^5\)数量级,直接优化掉了\(10^4\)的时间。

 

    而这个加速幅度是与\(n,m\)有关的,而一开始增长较快,后来变得很慢,每变化一次,\(i\)都要改变\(\frac im\)的数量级,这个数字每次对\(i\)平方,总增长的次数大概就是\(\log n\);而我这里为了保险起见没有推式子,就每次二分下一次变化边界在哪,当发现超过\(n\)时,在最后一段暴力求解即可。时间复杂度为\(O(m\log^2 n)\)。

 

    貌似取\(\frac im\)再稍微特判一下就不用多一个\(\log\)了啊…

 

    一般的约瑟夫问题直接列式子这样\(O(n)\)求解就可以了(吧

int solve(int n,int m)
{
    if(n==1)
        return 0;
    return (m+solve(n-1,m))%n;
}

 

Code:

#include<cstdio>
#include<cstring>
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        long long t=1,i=1;//i是当前的位置
        while(1)
        {
            long long l=1,r=n-i,mid;
            while(l<r)
            {
                mid=(l+r)>>1;
                if(t+mid*m>=(i+mid))
                    r=mid;
                else
                    l=mid+1;
            }
            if(i+l>n)
                break;
            i+=l;
            t=(t+l*m)%i;
            if(!t)
                t=i;
        }
        ++i;
        for(;i<=n;++i)
        {
            t=(t+m)%i;
            if(!t)
                t=i;
        }
        printf("%lld\n",t);
    }
    return 0;
}

 

2
说点什么

avatar
1 Comment threads
1 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
2 Comment authors
wjyyyViXbob Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
ViXbob
游客

您这道题在那个OJ上可以提交啊? 石头门好评!

/* */