对“输出 $\bmod p$ 意义下的答案”的一点疑问
  • 板块学术版
  • 楼主NGC5457
  • 当前回复10
  • 已保存回复10
  • 发布时间2023/2/18 17:07
  • 上次更新2023/10/24 00:27:09
查看原帖
对“输出 $\bmod p$ 意义下的答案”的一点疑问
241614
NGC5457楼主2023/2/18 17:07

如题。计算期望的题目常可以转化为“求出总权值和后除以总方案数”。其要求输出在 modp\bmod ppp 是质数)意义下的答案。对于大部分题目而言,总方案数 ss 仅仅是若干个 (Z/pZ)×(\mathbb{Z}/p\mathbb{Z})^{\times} 中的元素相乘得到的结果,自然有逆元 s1s^{-1};但另一些题目中这方案数是要通过加减等操作求出的,这时不一定保证有 s(Z/pZ)×s\in(\mathbb{Z}/p\mathbb{Z})^{\times}(即 s0s\neq 0)。

各位有遇到过这种情况么?如果这种情况真实存在,且 std 和选手程序的实现都没有注意到这个问题,那是否可以认为两者输出的答案均不正确?还是说,能够就题而论,证明总是有 s(Z/pZ)×s\in(\mathbb{Z}/p\mathbb{Z})^{\times}

(我在做 P4233 - 射命丸文的笔记,可以发现本题的“总方案数”就涉及了加减操作。)

2023/2/18 17:07
加载中...