Muriya Tensei

好久没来看看（所以第一题怎么构造，我第一反应就是 a_i = 1 << (2 * i)）

我超，知乎还真有这个问题的解，甚至两问都提到了，撞得彻底（没事，就当给正确答案站台了）

看似如此，但并没有这么简单 （比如这两问，其实就是有区别的，只考虑一个方面显然并不全面）

小羊遇到了一场试炼，与他一同参与的还有n个人。 试炼的内容如下： 1. 所有人（未被淘汰的人）站成一排，并从1开始按顺序编号 2. 随机等概率挑选一个编号为奇数的人淘汰 3. 所有人保持相对顺序不变，重复1,2直至只剩一人，这一人胜出 Q1：那么小羊站在几号位置，胜出的概率最大呢 如果试炼的内容改为： 1. 所有人（未被淘汰的人）站成一排，并从1开始按顺序编号 2. 随机等概率挑选一个编号为奇数的人淘汰，并给其余未被淘汰的人积1分 3. 所有人保持相对顺序不变，重复1,2直至只剩一人，一轮比赛完成，记录每个人的得分 4. 重复试炼m场（m足够大），积分高的人获胜 Q2：那么小羊站在几号位置，胜出的概率最大呢 例子： 如果共3人，编号后如下 1,2,3 进行一轮淘汰后（假设淘汰了1）变为 2,3 保持顺序不变重新编号 1,2 再进行第二轮淘汰（淘汰了1） 2 只剩一人，第一场试炼结束，此时最后剩下的是（初始的）3号选手，留至最后并积了两分

题目：https://sstm.moe/topic/323849-奇怪的算法挑战【第③期】池塘的鸭子/?do=findComment&comment=16223775 答案1：https://sstm.moe/topic/323849-奇怪的算法挑战【第③期】池塘的鸭子/?do=findComment&comment=16227568 答案2：https://sstm.moe/topic/323849-奇怪的算法挑战【第③期】池塘的鸭子/?do=findComment&comment=16235039

惊了，李永乐老师居然讲过这个题了。应该是10/18在ACM群里看到了转发的NGA帖子提到这个（4只鸭子的）题。然后简单延拓一下得到这个问题

坏了，原来李永乐老师讲过这个题了 这个题当初我也证明了好久。 我采用的个办法是，对于每个鸭子的分布可以看其关于圆心对称（或者说是旋转180°）的位置 那么本身n只鸭子就有了2n组点。简单分析一下就能知道，只有相邻的n组点可以被同一个半圆（180°）包括，而这组点的选取方法共有2n种。 概率就是 2n/2^n 即n/2^(n-1) 因此不光是半圆（180°）的情况，也可以这样映射（只是非整数的情况不确定对不对，感觉应该也是对的）就可以得到 n/m^(n-1) 这个式子

仔细看了下你的表达式。试图想出你是怎么化简的（无果）。但是结果吧，令n=n-1就对了好像（偏移了一个） 想了想这个假设。原题设是一个环的话，展成线应该会偏小吧，概率上会差多少呢（难道是(n+1)/2n）大胆猜测小心求证（

好久没来水贴了，最近看到了一个有意思的题目，甚至难倒了好几个大佬，来分享一下 （根本就不是算法题嘛，简单的概率题） 有一圆形池塘，在池塘中被遗留了n只小鸭子，小鸭子们等概率均匀分布在池塘中。 那么请问这n只鸭子们全部位于同一个半圆的概率是多少呢？ tip: 不妨想一想两只鸭子的情况 easy: n=2 mid: n=3, n=4 hard: n∈N+ ex: 除了半圆，即1/2圆的情况外，有没有办法考虑1/m圆的情况呢（m为正整数） ex2: 有没有办法考虑1/m圆的情况呢（m为大于一的正实数）（m可能会∈(1,2)）

好难啊，不会 能想到的思路1是二分答案+dfs的check，但是好像答案因为有差值1的约束，并不具有单调性 思路2是试图转化为二分图，想不懂，大概是只能处理min(c,n)== 2的情况 最后就是枚举size+dfs回溯了。总感觉问题是npc的，但又不会证明或者规约 （我说实话，就算数据量很小，指数级dfs回溯都不一定会写，好讨厌带约束的最值 这题我如果遇到，我就直接模拟退火了，生死由命成败在天

（看了看，BFS裸题吗） 那么就根据题意输入建立邻接表，广搜就可以啦 再优化点可以把反向邻接表建出来，跑双端BFS。 不过麻烦但是并不困难的内容就是根据最短距离来写出路径了（visit哈希表标记下路径转移即可） （虽然说是树的问题，事实上一个人的UID会在多个地方出现吧，并不能简单由下至上推出来，还是变成了有向有环图）

所有数x 求 (x|1)的异或和，剩下的就是单身狗啦（

可以说是相当完善了，用信息熵可以确认m≥⌈log(t/c+1) n⌉，并且用进制表示的方法很简单的也能描述出m=⌈log(t/c+1) n⌉的实现方法

有东西的.jpg，那么可以不盲猜来提供一下具体方法或者思路吗

我本来想说根本没在怕的来着，结果想到这只是外围（摔