Oi

题目链接 题意： 给你一张n个点n-1或n条边的带权无向图。从每个点出发一直走下去，不能重复经过某个点。问走过的路径长度的数学期望是多少？ N<=100000。图中至多只有一个环，并且环长不超过20。 ...

埃氏筛法：从2开始，找到第一个没有被筛的数，把它标记为素数，然后把它的2倍、3倍……筛掉。 复杂度O(nlogn)。 改进的埃氏筛法：从2开始，找到第一个没有被筛的数x，把它标记为素数，然后把它的x倍、x+1倍……筛掉。 复杂度O(nloglogn)。 ...

[题目链接][1] 题意：给定一个有向无环图（DAG），上面放有一些旗子，旗子可以重合，两个人轮流操作，每次可以把一个旗子从一个位置移动到相邻的位置，无法移动时输，询问先手是否必胜。 ...

题目链接 题意：有n堆石子，两人轮流操作，每次每个人可以从一堆中拿走若干个扔掉（必须），并且可以从中拿走一些分到别的有石子的堆里（可选），当一个人不能拿时这个人输。给定状态，问是否先手必胜。 ...

　阅读了《由感性认识到理性认识——透析一类搏弈游戏的解答过程》、《解析一类组合游戏》、《组合游戏略述——浅谈SG游戏的若干拓展及变形》这三篇论文，对组合游戏以及SG函数有了更深的理解。这篇文章摘下了这三篇论文的部分重要内容，以及部分我对组合游戏的理解。 ...

题目链接 题意介绍了一遍Nim取石子游戏，可以看上一篇文章详细介绍。 问当前状态的必胜走法个数，也就是走到必败状态的方法数。 我们设sg为所有个数的Xor值。 首先如果sg==0,它不可能有必胜走法，输出0. ...

题目链接 题意： 有一个数p=1，甲乙两人轮流操作，每次可以把p乘2-9中的一个数，给定一个n，当一个人操作后p>=n,那么这个人赢，问先手是否必胜。 ...

题目链接 题意：有n个硬币排成一圈，两个人轮流操作，每次可以取走一个或者相邻的连个硬币（只算最开始相邻的，取之后才相邻的不算），问先手必胜还是必败。 这个题可以证明若n>=3，则先手必败。 对称博弈 若n>=3，先手第一次必然把这个环拆成一个链，然后无论这条链长度的奇偶，后手总是可以把这条链分成两条相等的链，于是先手在一条链上做什么，后手就可以做什么。知道先手无法操作，后手胜。 ...

[题目链接][1] 有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，**一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。**最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。（中文题面，感动ing） ...

题目链接 题意：给一张n个点，m条边的带环无向连通图，求1-n路径上的权值Xor起来的期望。 即无向有环图上求路径Xor期望。 因为是Xor操作，所以我们可以按二进制位分开考虑。 设考虑到了第k位， 那么现在这个图中的边权只有0或1。 期望问题反着设一般比较好列方程，所以我们设f[i]为从i这个点走到nXor值是1的期望，显然f[n]==0。 ∑2^k*f[1]即为答案。 设P[i]为从i点出发的走每条边的概率，应该等于1/degree[i]。 我们可以列一组dp方程： f[i]=∑P[i]*f[j](w[j,i]==0)+∑P[i]*(1-f[j])(w[j,i]==1)。 若w[j,i]==0则从这条边走过来Xor值不变，w[j,i]==1则从这条边走过来Xor值取反，(1-f[j])即为在jXor值是0的期望。 ...