首页 > 其他分享 >E. Not a Nim Problem

E. Not a Nim Problem

时间:2024-08-17 18:31:21浏览次数:11  
标签:10 le Nim int Problem SG 节点 mathrm

E. Not a Nim Problem

Two players, Alice and Bob, are playing a game. They have $n$ piles of stones, with the $i$-th pile initially containing $a_i$ stones.

On their turn, a player can choose any pile of stones and take any positive number of stones from it, with one condition:

  • let the current number of stones in the pile be $x$. It is not allowed to take from the pile a number of stones $y$ such that the greatest common divisor of $x$ and $y$ is not equal to $1$.

The player who cannot make a move loses. Both players play optimally (that is, if a player has a strategy that allows them to win, no matter how the opponent responds, they will win). Alice goes first.

Determine who will win.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case consists of two lines:

  • the first line contains a single integer $n$ ($1 \le n \le 3 \cdot 10^5$);
  • the second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^7$).

Additional constraint on the input: the sum of $n$ across all test cases does not exceed $3 \cdot 10^5$.

Output

For each test case, output Alice if Alice wins, or Bob if Bob wins.

Example

Input

3
3
3 2 9
4
3 3 6 1
5
1 2 3 4 5

Output

Bob
Alice
Bob

 

解题思路

  借这题学一下 SG 函数。SG 函数是解决像取石子这类博弈论问题的一大利器。

  以取石子游戏为例,我们把每一堆石子可能发生的变化用 DAG 来表示,其中节点代表一个局面,边代表可以从一个局面转移到另一个局面。比如以本题的规则对 $3$ 堆石子 $[1,3,4]$ 进行游戏得到的 DAG 如下:

  每个节点(局面)$u$ 的 SG 值就是其后继节点 $v_1, \ldots v_m$ 的 SG 值的 $\mathrm{mex}$ 值,即 $\mathrm{SG}(u) = \mathrm{mex}\{ \mathrm{SG}(v_1), \ldots, \mathrm{SG}(v_m) \}$,其中定义集合 $S$ 的 $\mathrm{mex}$ 值为不属于 $S$ 中的最小非负整数。上图中每个节点的 SG 值如下所示:

  可以发现每一个 DAG 都只有一个起点 $S$,因此如果 $\mathrm{SG}(S) \ne 0$ 则先手必胜,否则 $\mathrm{SG}(S) = 0$ 则先手必败。这是因为任意 SG 不为 $0$ 的节点都可以走到 SG 为 $0$ 的节点,而任意 SG 为 $0$ 的节点都走不到 SG 不为 $0$ 的节点(否则当前节点的 SG 值就大于 $0$ 了),又因为所有的终点(即出度为 $0$ 的点)的 SG 值为 $0$,对应着先手必败,因此结论得证。

  而如果有 $n$ 个 DAG,每个 DAG 的起点分别为 $S_1, \ldots, S_n$,那么整个游戏先手必胜的条件是 $\mathrm{SG}(S_1) \oplus \cdots \oplus \mathrm{SG}(S_n) \ne 0$,否则 $\mathrm{SG}(S_1) \oplus \cdots \oplus \mathrm{SG}(S_n) = 0$ 则先手必败。证明的方法与 Nim 游戏十分相似。

  回到本题,令 $A = \max\{ a_i \}$,显然我们需要求出 $1 \sim A$ 的 SG 值,然后根据 $\mathrm{SG}(a_1) \oplus \cdots \oplus \mathrm{SG}(a_n)$ 判断先手必胜还是必败,时间复杂度为 $O(A^2 \log{A})$。由于 $A$ 最大取 $10^7$,因此这种做法显会然超时。

  我们先打表看看 SG 值是否满足某些规律,以下是求出 $1 \sim 100$ 的 SG 值的程序和结果:

打表代码
#include <bits/stdc++.h>
using namespace std;

const int N = 105;

int f[N];

int dfs(int u) {
    if (f[u] != -1) return f[u];
    set<int> st;
    for (int i = 1; i <= u; i++) {
        if (__gcd(i, u) == 1) st.insert(dfs(u - i));
    }
    for (int i = 0; true; i++) {
        if (!st.count(i)) return f[u] = i;
    }
}

int main() {
    memset(f, -1, sizeof(f));
    for (int i = 1; i <= 100; i++) {
        cout << "SG(" << i << ") = " << dfs(i) << '\n';
    }
    
    return 0;
}
打表结果
SG(1) = 1
SG(2) = 0
SG(3) = 2
SG(4) = 0
SG(5) = 3
SG(6) = 0
SG(7) = 4
SG(8) = 0
SG(9) = 2
SG(10) = 0
SG(11) = 5
SG(12) = 0
SG(13) = 6
SG(14) = 0
SG(15) = 2
SG(16) = 0
SG(17) = 7
SG(18) = 0
SG(19) = 8
SG(20) = 0
SG(21) = 2
SG(22) = 0
SG(23) = 9
SG(24) = 0
SG(25) = 3
SG(26) = 0
SG(27) = 2
SG(28) = 0
SG(29) = 10
SG(30) = 0
SG(31) = 11
SG(32) = 0
SG(33) = 2
SG(34) = 0
SG(35) = 3
SG(36) = 0
SG(37) = 12
SG(38) = 0
SG(39) = 2
SG(40) = 0
SG(41) = 13
SG(42) = 0
SG(43) = 14
SG(44) = 0
SG(45) = 2
SG(46) = 0
SG(47) = 15
SG(48) = 0
SG(49) = 4
SG(50) = 0
SG(51) = 2
SG(52) = 0
SG(53) = 16
SG(54) = 0
SG(55) = 3
SG(56) = 0
SG(57) = 2
SG(58) = 0
SG(59) = 17
SG(60) = 0
SG(61) = 18
SG(62) = 0
SG(63) = 2
SG(64) = 0
SG(65) = 3
SG(66) = 0
SG(67) = 19
SG(68) = 0
SG(69) = 2
SG(70) = 0
SG(71) = 20
SG(72) = 0
SG(73) = 21
SG(74) = 0
SG(75) = 2
SG(76) = 0
SG(77) = 4
SG(78) = 0
SG(79) = 22
SG(80) = 0
SG(81) = 2
SG(82) = 0
SG(83) = 23
SG(84) = 0
SG(85) = 3
SG(86) = 0
SG(87) = 2
SG(88) = 0
SG(89) = 24
SG(90) = 0
SG(91) = 4
SG(92) = 0
SG(93) = 2
SG(94) = 0
SG(95) = 3
SG(96) = 0
SG(97) = 25
SG(98) = 0
SG(99) = 2
SG(100) = 0

  可以发现以下规律:

  • 如果 $x$ 是偶数,那么 $\mathrm{SG}(x) = 0$。
  • 如果 $x$ 是从 $3$ 开始的质数,那么 $\mathrm{SG}(x) = p(x)$,其中 $p(x)$ 指 $x$ 在所有质数中的第几个。
  • 如果 $x$ 是奇合数,那么 $\mathrm{SG}(x) = \mathrm{SG}(d(x))$,其中 $d(x)$ 指 $x$ 的最小质因子。
  • 特别的,$\mathrm{SG}(1) = 1$,$\mathrm{SG}(2) = 0$。

  因此我们就可以用欧拉筛以 $O(A)$ 的复杂度求出 $1 \sim A$ 的 SG 值。

  AC 代码如下,时间复杂度为 $O(A)$:

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 1e7 + 5;

int primes[N], cnt;
bool vis[N];
int f[N];

void get_prime(int n) {
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            primes[cnt++] = i;
            f[i] = cnt;
        }
        for (int j = 0; primes[j] * i <= n; j++) {
            int t = primes[j] * i;
            vis[t] = true;
            if (t & 1) f[t] = f[primes[j]];
            if (i % primes[j] == 0) break;
        }
    }
    f[1] = 1, f[2] = 0;
}

void solve() {
    int n;
    cin >> n;
    int ret = 0;
    while (n--) {
        int x;
        cin >> x;
        ret ^= f[x];
    }
    cout << (ret ? "Alice" : "Bob") << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    get_prime(N - 1);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

 

参考资料

  第四章 数学知识(四):https://www.acwing.com/file_system/file/content/whole/index/content/4810/

  公平组合游戏 - OI Wiki:https://oi-wiki.org/math/game-theory/impartial-game/

  Educational Codeforces Round 169 Editorial:https://codeforces.com/blog/entry/132790

标签:10,le,Nim,int,Problem,SG,节点,mathrm
From: https://www.cnblogs.com/onlyblues/p/18364766

相关文章

  • Resume: How to Write a Minimalistic CV in LaTeX: Step-by-step Guide
    HowtoWriteaMinimalisticCVinLaTeX:Step-by-stepGuidehttps://latex-tutorial.com/cv-latex-guide/HowtoWriteaMinimalisticCVinLaTeX:Step-by-stepGuideWrittenbyAdmininCVlatexLearnhowtowriteandcustomizeaminimalisticcurriculumvit......
  • 题解:AT_arc181_b [ARC181B] Annoying String Problem
    思路首先我们可以根据两个字符串算出另外一个字符串\(T\)的长度。算出来之后,因为我们要满足等式两边完全相等,所以很容易得出这两个字符串应该都是由一些公共的字串拼接而成的。设\(S\)串中最小的周期为\(P\)。所以应该满足\(|P|\Large{\mid}\normalsize\gcd(|S|,|T|)\)......
  • ChatGPT Is a Knowledgeable but Inexperienced Solver: An Investigation of Commons
    文章目录题目摘要简介什么是常识GPT能否有效回答常识问题?GPT是否知道回答问题的常识性知识?GPT是否具备常识性知识?GPT能否有效利用语境中的常识进行推理?相关工作结论与讨论题目ChatGPT是一个知识渊博但缺乏经验的解决者:对大型语言模型中常识问题的调查论文地......
  • WPF Animation 动画变化值的监控
    WPF动画XXXAnimation即关键类继承制AnimationBase的动画类线性插值动画主要属性FromToDurationAcceleratorDecceleratorFillBehavior等这些常用属性里不做介绍,主要介绍一下几个故事板属性,以备忘记.名称说明Completed动画到达终点时触发,该事件中可以......
  • D. Another Problem About Dividing Numbers
    原题链接题意有两个数\(a,b\)每次可以拿走其中一个数的若干个质因子,请问恰好\(k\)次操作后能否使\(a=b\)分析假设\(a,b\)最后到达的是\(c\),那么\(\frac{a}{c}\)的质因子个数加上\(\frac{b}{c}\)的质因子个数一定大于等于\(k\)(为什么可以大于?因为一次操作可以多......
  • P1001 A+B Problem(整活-dijstra堆优化)
    OK啊,这就是普通的\(a+b\)嘛这是一道十分淼的题目,乍一看,这不就是dijstra堆优化的模板题吗?首先,建立三个节点,两条线行,OK开始Code#include<bits/stdc++.h>usingnamespacestd;constlonglongN=99999,M=999999;typedefpair<longlong,longlong>PII;priority_......
  • Manim的一个用于数学动画的 Python 库中渲染代码的功能。
       Code 函数是Manim(一个强大的数学动画库)中的一个重要工具,旨在将代码片段以视觉化的方式呈现。在教育和演示场合中,向观众展示算法或代码逻辑时,清晰的视觉效果是必不可少的。通过 Code 函数,用户可以轻松地将特定编程语言的代码导入,并且自定义其外观,包括字体、颜色、背景......
  • 【Material-UI】Floating Action Button (FAB) 详解:动画效果 (Animation)
    文章目录一、FAB按钮的动画概述1.默认动画效果2.多屏幕横向切换时的动画二、FAB动画效果的实现1.代码示例:跨标签页的FAB动画2.代码解析3.多个FAB的切换三、动画效果的最佳实践四、总结在现代网页设计中,动画不仅提升了用户界面的动态感,还增强了用户的交......
  • Character Animator 2022软件:让角色动画制作变得轻松愉悦
    在当今这个多媒体内容盛行的时代,动画已经成为了人们获取信息和娱乐的重要途径。为了满足广大用户对高质量角色动画制作的需求,Adobe公司推出了一款备受好评的角色动画软件——CharacterAnimator2022。今天,我们就来详细了解一下这款功能强大、易于使用的角色动画神器。Chara......
  • Codeforces Round 903 (Div. 3) F. Minimum Maximum Distance
    https://codeforces.com/contest/1881/problem/F不难发现一件事情,我们这里最后的答案所在的点是1和3号点。我们有没有发现一个性质:就是这两个点都是红点间的路径上的,而且最后的答案就是最长的红点间的距离的长度除以二上取整。那么,我们怎么找到最长的红点间的距离呢?很显......