御坂御坂题解(出自北航校赛) 约瑟夫环问题高效解决方案

御坂御坂

题目如下：

由提示可定义函数f(x):

f(1)=0

当x>1时有

f(x)=(f(x-1)+3)mod x

这个函数的意思是，f(x)是x个人的时候最后一个剩下的妹妹的编号

f(x+1)的时候是第0个人先出局了，这样子就只剩下了x个妹妹，然后第3个人就变成了f(x)的第一个出局的人，剩余人数也是x个人，那么把御坂妹妹的编号转换一下就是f(x+1)的游戏结果。

所以得出公式f(x)=(f(x-1)+3)mod x

关于这个公式我们打个表不难发现，这个公式是分段线性递增的，又因为mod每次+1而f(x)是每次+3，所以每隔x/2次增长后，f(x)会被mod减小一次，所以每经过x*3/2后，f(x)会被清零一次

就是说分段的时候x每次会增加x/2，也就是x=(3/2)*x

也就是说x是指数级递增的。

所以你可以求f是哪一段的，又因为是线性函数，所以可以直接求值。我们就能在log(n)的复杂度得到f(x)的值

然后这题的答案就是暴力跑m次f(x)来求答案，但是在log(m)次之内中一定会变成f(x)+1=f(f(x)+1)的情况，就可以直接跳出得到答案了

这题的做法

1、 O(log(n)*log(m))

log(n)的复杂度求f(n),log(m)次递归求解。

log(n)求f(n)的做法(1)

 1 #include<math.h>
 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<stdlib.h>
 5 #include<algorithm>
 6 using namespace std;
 7 typedef long long ll;
 8 /*f[1]=0;
 9 f[n]=(f[n-1]+3)%n
10 c[n]=c[f[n]+1]*/
11 ll f(ll n)
12 {
13     ll ans=0,m=1;
14     while(m<n)
15     {
16         ll res=m-ans;
17         ll add=res/2+(res%2);
18         if(m+add>n)break;
19         m+=add;
20         ans=ans+add*3-m;
21     }
22     return (ans+(n-m)*3)%n;
23 }
24 ll c(ll n,ll m,ll pre)
25 {
26     if(pre==n)return pre;
27     if(m==0)return n;
28     return c(f(n)+1,m-1,n);
29 }
30 int main()
31 {
32     ll t;
33     scanf("%lld",&t);
34     while(t--)
35     {
36         ll n,m;
37         scanf("%lld%lld",&n,&m);
38         printf("%lld
",c(n,m,n+1));
39     }
40     return 0;
41 }

View Code

log(n)求f(n)的做法(2)::这个方法的原理请参考:https://www.cnblogs.com/weidiao/p/5966204.html（这个效率比上面的低一些，因为是递归所以比较慢，(1)和(2)只不过一个是正着推一个是反着推）

 1 #include<math.h>
 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<stdlib.h>
 5 #include<algorithm>
 6 using namespace std;
 7 typedef long long ll;
 8 /*f[1]=0;
 9 f[n]=(f[n-1]+3)%n
10 c[n]=c[f[n]+1]*/
11 ll f(ll n)
12 {
13     if(n==1)return 0;
14     if(n==2)return 1;
15     ll temp=f(n-n/3);
16     return (temp+((temp-n%3)<0?0:(temp-n%3))/2+n-n%3)%n;
17 }
18 ll c(ll n,ll m,ll pre)
19 {
20     if(pre==n)return pre;
21     if(m==0)return n;
22     return c(f(n)+1,m-1,n);
23 }
24 int main()
25 {
26     ll t;
27     scanf("%lld",&t);
28     while(t--)
29     {
30         ll n,m;
31         scanf("%lld%lld",&n,&m);
32         printf("%lld
",c(n,m,n+1));
33     }
34     return 0;
35 }

View Code

2、O(log(log(n))*log(m)

对f(n)进行打表，预处理出来一个分段的表，然后在表上进行二分求f(n)，这样子求f(n)就变成了log(log(n))的复杂度。所以时间复杂度为log(log(n))*log(m)

打表代码如下：

 1 void db()
 2 {
 3     ll x=1;
 4     ll f=0;
 5     while(x<=(ll)1e18)
 6     {
 7         printf("%lld %lld
",x,f);
 8         ll res=x-f;
 9         ll add=(res+1)/2;
10         x+=add;
11         f=f+add*3-x;
12     }
13 }

View Code

ac代码如下：

 1 #include<math.h>
 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<stdlib.h>
 5 #include<algorithm>
 6 using namespace std;
 7 typedef long long ll;
 8 /*f[1]=0;
 9 f[n]=(f[n-1]+3)%n
10 c[n]=c[f[n]+1]*/
11 ll fj[]={1ll,2ll,3ll,4ll,6ll,9ll,14ll,21ll,31ll,47ll,70ll,105ll,158ll,237ll,355ll,533ll,799ll,1199ll,1798ll,2697ll,4046ll,6069ll,9103ll,13655ll,20482ll,30723ll,46085ll,69127ll,103691ll,155536ll,233304ll,349956ll,524934ll,787401ll,1181102ll,1771653ll,2657479ll,3986219ll,5979328ll,8968992ll,13453488ll,20180232ll,30270348ll,45405522ll,68108283ll,102162425ll,153243637ll,229865456ll,344798184ll,517197276ll,775795914ll,1163693871ll,1745540806ll,2618311209ll,3927466814ll,5891200221ll,8836800331ll,13255200497ll,19882800745ll,29824201118ll,44736301677ll,67104452515ll,100656678773ll,150985018159ll,226477527239ll,339716290858ll,509574436287ll,764361654431ll,1146542481646ll,1719813722469ll,2579720583704ll,3869580875556ll,5804371313334ll,8706556970001ll,13059835455001ll,19589753182502ll,29384629773753ll,44076944660629ll,66115416990944ll,99173125486416ll,148759688229624ll,223139532344436ll,334709298516654ll,502063947774981ll,753095921662471ll,1129643882493707ll,1694465823740560ll,2541698735610840ll,3812548103416260ll,5718822155124390ll,8578233232686585ll,12867349849029878ll,19301024773544817ll,28951537160317225ll,43427305740475838ll,65140958610713757ll,97711437916070635ll,146567156874105953ll,219850735311158929ll,329776102966738394ll,494664154450107591ll,741996231675161386ll};
12 ll as[]={0,1,1,0,0,0,1,1,0,1,0,0,1,1,0,1,0,1,0,0,1,1,0,1,0,0,1,0,1,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,0,1,0,1,1,1,1,1,0,0,1,1,0,1,0,1,1,0,1,0,1,0,0,1,0,0,1,1,1,1,0,1,1,0,1,1,1,1,1,1,0,1,0,0,0,0,0,1,1,0,1,1,0,1,0,1,1,0};
13 const int xn=102;
14 ll f(ll n)
15 {
16     int l=-1,r=xn;
17     while(l+1<r)
18     {
19         int mid=(l+r)/2;
20         if(fj[mid]>n)
21             r=mid;
22         else l=mid;
23     }
24     return as[l]+(n-fj[l])*3;
25 }
26 ll c(ll n,ll m,ll pre)
27 {
28     if(pre==n)return pre;
29     if(m==0)return n;
30     return c(f(n)+1,m-1,n);
31 }
32 void db()
33 {
34     ll x=1;
35     ll f=0;
36     while(x<=(ll)1e18)
37     {
38         printf("%lld %lld
",x,f);
39         ll res=x-f;
40         ll add=(res+1)/2;
41         x+=add;
42         f=f+add*3-x;
43     }
44 }
45 int main()
46 {
47     ll t;
48     scanf("%lld",&t);
49     while(t--)
50     {
51         ll n,m;
52         scanf("%lld%lld",&n,&m);
53         printf("%lld
",c(n,m,n+1));
54     }
55     return 0;
56 }

View Code