2018-10-07 Gym-101864A丨二阶约瑟夫环丨想法

来源：cnblogs　　作者：伍玖似十九　　时间：2018/10/8 8:49:31　　对本文有异议

题意：

多组样例，每组输入X L N，代表取1到rand(L,N)做二阶约瑟夫环（最后剩下一个人不处罚），假设每种可能性概率相等，求X位置上的人不被处罚的概率。

思路：

一开始很混，因为n的范围到1e15，要做得巧，首先对不被惩罚的情况，有两种：

1.成为约瑟夫环的剩下的人。

2.没有被选入环（X在某些情况大于>rand(L,N)）。

然后需要一些结论：

https://en.wikipedia.org/wiki/Josephus_problem#k=2

需要知道的是，对于二阶约瑟夫环，偶数位的人必出局，那么如何计算奇数位的情况呢？对于人数为n=2^i+j的环，存活位x=2*j+1。

具体证明参考维基百科。知道这些有什么用呢？本题已知，需要存活的位置x，以及参与环的人数区间[L,N]，我们需要求不被惩罚的概率，也就是找出[L,N]的参与人数中，有那些是对x有利的，找出有利情况的数量（包括不加入环和从环中幸存），就可以了。

所以可以利用n=2^i+j枚举有利条件的所有情况，最后处以gcd就是答案。

虽然代码迷之短，但是还是有很多细节需要考量的（比如逆推的n肯定要大于等于x）。

参考代码：

#include<stdio.h>
#include<algorithm>
typedef long long ll;
int T,Ti;
ll x,l,n;
int main(){
    scanf("%d",&T);
    while(Ti++<T){
        scanf("%lld%lld%lld",&x,&l,&n);
        ll sum=std::max(0ll,x-l);
        //when x>l,x won't be list in these rounds;
        if(x&1){
            ll j=(x-1)/2;
            //safe position x=2*j+1 when n=2^k+j,check every n;
            for(ll i=1;i+j<=n;i<<=1){
                if(i+j<l||i+j<x)continue;
                sum++;
            }
        }else if(x<=l){
            //x is even and can be listed in every round;
            printf("Case %d: 0/1\n",Ti);
            continue;
        }
        ll gcd=std::__gcd(sum,n-l+1);
        printf("Case %d: %lld/%lld\n",Ti,sum/gcd,(n-l+1)/gcd);
    }
    return 0;
}
/*
3
1 1 1
2 3 10
4 1 7
*/

View Code
 