HBC233503[JSOI2016]灯塔,枚举No Game No Life题解

想要检验自己的编程水平？来试试全网最全C++题库，让您在挑战中不断进步。

Alice 和 Bob 在玩游戏， 在他们面前有一张 nnn 个点，mmm 条边的有向无环图，每个点有若干芯片，数量为 aia_iai，Alice 和 Bob 轮流操作，Alice 先手，定义玩家的一次操作为将图上的某一顶点的一个芯片根据有向边移到另外一个顶点上，每人每次只能操作一次，如果一个人不能操作，那么他输掉游戏， 在游戏开始后，每一秒在图上都会发生如下的操作： 1. 在 [1,n+1

Alice 和 Bob 在玩游戏。 在他们面前有一张 nnn 个点，mmm 条边的有向无环图，每个点有若干芯片，数量为 aia_iai​。Alice 和 Bob 轮流操作，Alice 先手。定义玩家的一次操作为将图上的某一顶点的一个芯片根据有向边移到另外一个顶点上。每人每次只能操作一次。如果一个人不能操作，那么他输掉游戏。 在游戏开始后，每一秒在图上都会发生如下的操作： 1. 在 [1,n+1][1,n+1][1,n+1] 范围内等概率选取一个整数 vvv。 2. 如果 v≤nv leq nv≤n，那么在 vvv 顶点放置一个芯片，这一秒操作结束。 3. 如果 v=n+1v = n + 1v=n+1，那么 Alice 和 Bob 开始游戏，游戏结束后所有操作停止。 保证 Alice 和 Bob 都绝对聪明。 现在请你求出 Alice 赢的概率。对 998244353998244353998244353 取模。 即若概率为最简分数 pqdfrac{p}{q}qp​（保证 q≢0 mod 998244353q not equiv 0 bmod 998244353q​≡0mod998244353），你只需要输出 xxx 使得 qx≡p mod 998244353qx equiv p bmod 998244353qx≡pmod998244353，可以证明这样的 xxx 是唯一的。

标签： HBC233503[JSOI2016]灯塔 枚举No Game No Life题解