房间内有 nnn 张椅子从 1 至 nnn 标号，有 nnn 个人从 1 至 nnn 标号，他们按标号 1→n1 to n1→n 的顺序进入房间选位置坐，当第 iii 个人坐下后，第 i+1i + 1i+1 个人才会进入房间选位置坐， 第 iii 个人会在标号在区间 [1,min(n,i+1)][1,~ min(n, ~i + 1)][1,min(n,i+1)] 范围内的椅子等概率随机选一张没有
房间内有 nnn 张椅子从 1 至 nnn 标号，有 nnn 个人从 1 至 nnn 标号，他们按标号 1→n1 to n1→n 的顺序进入房间选位置坐。当第 iii 个人坐下后，第 i+1i + 1i+1 个人才会进入房间选位置坐。 第 iii 个人会在标号在区间 [1, min(n, i+1)][1,~ min(n, ~i + 1)][1, min(n, i+1)] 范围内的椅子等概率随机选一张没有人坐的椅子坐下。 最终有 xxx 人，他们自身的标号与他们所坐椅子的标号相同，求 xxx 的期望，对 998244353 取模。 可以证明，最终计算出来的期望可以被表示为分数形式 PQfrac{P}{Q}QP，其中 P,QP, QP,Q 为整数且 Q≢0(mod 998244353)Q notequiv0(mod 998244353)Q≡0(mod998244353)。输出 P⋅Q−1mod 998244353P cdot Q^{-1} mod 998244353P⋅Q−1mod998244353 即可。换句话说，输出这样一个整数 0≤x<9982443530 le x < 9982443530≤x<998244353 满足 x⋅Q≡P(mod 998244353)x cdot Q equiv P(mod 998244353)x⋅Q≡P(mod998244353)。 上式中的 ≡equiv≡ 符号表示同余符号。
标签： HBC246842I 炎炎消防队 模拟退火座位题解
