首页 > 试题广场 >

游戏

[编程题]游戏
小N和小O在玩游戏。他们面前放了n堆石子,第i堆石子一开始有ci颗石头。他们轮流从某堆石子中取石子,不能不取。最后无法操作的人就输了这个游戏。但他们觉得这样玩太无聊了,更新了一下规则。具体是这样的:对于一堆有恰好m颗石子的石头堆,假如一个人要从这堆石子中取石子,设他要取石子数为d,那么d必须是m的约数。最后还是无法操作者输。
现在小N先手。他想知道他第一步有多少种不同的必胜策略。一个策略指的是,从哪堆石子中,取走多少颗石子。只要取的那一堆不同,或取的数目不同,都算不同的策略。

输入描述:
第一行一个整数n。
接下来一行n个整数,分别代表每堆石子的石子数目。
数据保证输入的所有数字都不超过105,均大于等于1,且为整数。


输出描述:
一行一个整数代表小$N$第一步必胜策略的数量。
示例1

输入

10
47 18 9 36 10 1 13 19 29 1

输出

7
头像 白色L号谢谢
发表于 2020-07-07 21:35:10
SG定理:n个有向图游戏组成的组合游戏当且仅当SG值异或和等于0时先手必输,否则先手必胜。直接求出每个状态的SG值,最后遍历每堆石头第一次取的情况,如果能满足异或和等于0即留给对手一个必败状态,则方案数加1。 #include <bits/stdc++.h> #include <u 展开全文
头像 ruoye123456
发表于 2024-04-01 22:16:31
首先需要预处理出x个石子能够进行的操作数,存到链表e[x]里面该步骤为n 对每一堆石子求sg函数,对每一堆石子枚举考虑该步骤能否是sg的异或为0,可以则方案数加一 注意:在分解操作中两个约数相同要排除,该操作不会影响sg,但会是方案数重复计算 #include<bits/stdc++.h> 展开全文