#P6755. [2019山东冬令营]游戏
[2019山东冬令营]游戏
[2019山东冬令营]游戏
题目描述
Alice 和 Bob 在黑板上写下 个正整数 ,轮流操作,Alice 先手。
每次操作选择一个位置,将该位置的整数替换成它的一个正真因数,即选择 满足 且 ,并令 。不能操作的人输。
两人都会采用最优策略:只要当前局面存在必胜走法,就一定选择能保持自己必胜的走法。
请回答:
- 谁会获胜?
- 若 Alice 必胜,她第一步有多少种走法可以保证自己最终获胜?
- 若 Alice 必败,她在第一步的所有合法走法中等概率随机选择一种。求此后 Bob 的下一步中,能够保持必胜的走法数量的期望,以最简分数表示。
一次走法由“选择的位置”和“替换后的真因数”共同确定。即使两个位置上的数相同,选择不同位置仍是不同走法。
输入格式
第一行一个正整数 。
第二行 个正整数 。
输出格式
第一行输出 Alice 或 Bob,表示获胜者。
若 Alice 必胜,第二行输出一个整数,表示她第一步的必胜走法数。
若 Bob 必胜,第二行输出两个整数 ,表示所求期望为最简分数 。若初始局面没有任何合法操作,约定期望为 0,第二行输出 0 1。
样例输入 1
4
6 2 3 3
样例输出 1
Alice
2
样例解释 1
Alice 将第一个数 改成 或 ,都可以保证获胜,其余首步不能保证获胜。
样例输入 2
3
2 6 12
样例输出 2
Bob
4 3
样例解释 2
Alice 共可选择 种首步。相应局面及 Bob 下一步的必胜走法数如下:
| Alice 操作后的局面 | Bob 的必胜走法数 |
|---|---|
因此期望为 。
样例输入 3
6
6 6 6 6 6 6
样例输出 3
Bob
25 3
数据范围
所有数据满足 ,。
- 的数据满足 。
- 的数据满足 (包含上述 )。
- 另外 的数据中, 在 到 中等概率随机生成。
- 另外 的数据保证获胜者为 Alice。