HBC253623Gitignore,递归Kevin逛超市题解 （氧气少年找出nnn件物品）

全网最全C++题库，助您快速提升编程技能！题库丰富多样，涵盖各个领域，让您在练习中不断成长！

氧气少年在逛超市，他总共买了nnn件物品，当他走到超市出口时，出口的报警器响了起来，已知恰好有一件物品使报警器报警，并且这件使报警器报警的物品于nnn件物品中随机分布，现在氧气少年想找出这件使报警器报警的物品，他采取这样的方式找出这件物品：。令集合B={Amin,Amin+1Amin+Amax2}B=lbrace A_{min},A_{min}+1cdots lfloor frac{A_{min}+A_{max}}{2} rfloorrbraceB={Amin,Amin+12Amin+Amax}，然后执行步骤 2；将集合BBB中对应编号的物品通过报警器，如果报警，并且∣B∣=1|B|=1∣B∣=1，则结束；

氧气少年在逛超市。 他总共买了 nnn 件物品，当他走到超市出口时，出口的报警器响了起来。 已知恰好有一件物品使报警器报警，并且这件使报警器报警的物品于 nnn 件物品中随机分布。现在氧气少年想找出这件使报警器报警的物品，他采取这样的方式找出这件物品： 将这 nnn 件物品标号为 1…n1dots n1…n。 定义集合 SSS 中最小的元素为 Smin⁡S_{min}Smin​，SSS 中最大的元素为 Smax⁡S_{max}Smax​，SSS 包含的元素数量为 ∣S∣|S|∣S∣。 氧气少年先将所有物品的编号放入集合 AAA，即令集合 A={1,2,⋯n}A=lbrace 1,2,cdots n rbraceA={1,2,⋯n}。然后他会进行下面的操作：  令集合 B={Amin⁡,Amin⁡+1⋯⌊Amin⁡+Amax⁡2⌋}B=lbrace A_{min},A_{min}+1cdots lfloor frac{A_{min}+A_{max}}{2} rfloorrbraceB={Amin​,Amin​+1⋯⌊2Amin​+Amax​​⌋}，然后执行步骤 2；  将集合 BBB 中对应编号的物品通过报警器。  如果报警，并且 ∣B∣=1|B|=1∣B∣=1，则结束；  如果报警，并且 ∣B∣>1|B|>1∣B∣>1，则令 A=BA=BA=B，然后回到步骤 1；  如果没报警，则令集合 A={⌊Amin⁡+Amax⁡2⌋+1,⌊Amin⁡+Amax⁡2⌋+2⋯Amax⁡}A=lbrace lfloor frac{A_{min}+A_{max}}{2}rfloor+1, lfloor frac{A_{min}+A_{max}}{2}rfloor+2cdots A_{max}rbraceA={⌊2Amin​+Amax​​⌋+1,⌊2Amin​+Amax​​⌋+2⋯Amax​}，然后回到步骤 1。 氧气少年想知道，从他开始查找物品开始，到他找到这件物品为止，氧气少年将物品通过报警器的次数（即：步骤 2 执行次数）的期望。 可以证明，答案可以表示成 pqfrac{p}{q}qp​ 的形式。其中，p≥0,q≥1,gcd⁡(p,q)=1,qmod  998244353≠0pgeq 0,qgeq 1,gcd(p,q)=1,qmod 998244353neq 0p≥0,q≥1,gcd(p,q)=1,qmod998244353​=0。因此你只需输出 p⋅q998244351mod  998244353pcdot q^{998244351}mod 998244353p⋅q998244351mod998244353 即可。

不断学习，不断挑战，才能在编程领域中脱颖而出！全网最全C++题库，助您成为编程高手！

标签： HBC253623Gitignore 递归Kevin逛超市题解