#P6755. [2019山东冬令营]游戏

    ID: 6575 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 6 上传者: 标签>博弈论数论组合数学动态规划CF2100筛法构造

[2019山东冬令营]游戏

[2019山东冬令营]游戏

题目描述

Alice 和 Bob 在黑板上写下 kk 个正整数 n1,n2,…,nkn_1,n_2,\ldots,n_k,轮流操作,Alice 先手。

每次操作选择一个位置,将该位置的整数替换成它的一个正真因数,即选择 dd 满足 d∣nid\mid n_i 且 1≤d<ni1\le d<n_i,并令 ni=dn_i=d。不能操作的人输。

两人都会采用最优策略:只要当前局面存在必胜走法,就一定选择能保持自己必胜的走法。

请回答:

  1. 谁会获胜?
  2. 若 Alice 必胜,她第一步有多少种走法可以保证自己最终获胜?
  3. 若 Alice 必败,她在第一步的所有合法走法中等概率随机选择一种。求此后 Bob 的下一步中,能够保持必胜的走法数量的期望,以最简分数表示。

一次走法由“选择的位置”和“替换后的真因数”共同确定。即使两个位置上的数相同,选择不同位置仍是不同走法。

输入格式

第一行一个正整数 kk。

第二行 kk 个正整数 n1,n2,…,nkn_1,n_2,\ldots,n_k。

输出格式

第一行输出 Alice 或 Bob,表示获胜者。

若 Alice 必胜,第二行输出一个整数,表示她第一步的必胜走法数。

若 Bob 必胜,第二行输出两个整数 p,qp,q,表示所求期望为最简分数 p/qp/q。若初始局面没有任何合法操作,约定期望为 0,第二行输出 0 1。

样例输入 1

4
6 2 3 3

样例输出 1

Alice
2

样例解释 1

Alice 将第一个数 66 改成 22 或 33,都可以保证获胜,其余首步不能保证获胜。

样例输入 2

3
2 6 12

样例输出 2

Bob
4 3

样例解释 2

Alice 共可选择 99 种首步。相应局面及 Bob 下一步的必胜走法数如下:

Alice 操作后的局面 Bob 的必胜走法数
(1,6,12)(1,6,12) 22
(2,1,12)(2,1,12)
(2,2,12)(2,2,12) 11
(2,3,12)(2,3,12)
(2,6,1)(2,6,1) 22
(2,6,2)(2,6,2) 11
(2,6,3)(2,6,3)
(2,6,4)(2,6,4)
(2,6,6)(2,6,6)

因此期望为 (2+2+1+1+2+1+1+1+1)/9=4/3(2+2+1+1+2+1+1+1+1)/9=4/3。

样例输入 3

6
6 6 6 6 6 6

样例输出 3

Bob
25 3

数据范围

所有数据满足 1≤k≤1061\le k\le10^6,1≤ni≤1061\le n_i\le10^6。

  • 30%30\% 的数据满足 k≤5, ni≤10k\le5,\ n_i\le10。
  • 50%50\% 的数据满足 k≤100, ni≤100k\le100,\ n_i\le100(包含上述 30%30\%)。
  • 另外 10%10\% 的数据中,nin_i 在 11 到 10610^6 中等概率随机生成。
  • 另外 20%20\% 的数据保证获胜者为 Alice。

原题面 PDF