洞察探索国产操作系统如何助力企业在物联网领域实现高效管理与合规运营,提升数字化转型的能力。
660
2022-08-29
NKOI Round 5 1.摩拜单车
1.摩拜单车(mobike.cpp/c/pas) 【问题描述】 为了回馈用户,摩拜单车计划推行一款红包。 每位用户每次骑红包车2分钟以上都可以获得一个红包,红包有且仅有以下 2种: (1)现金红包,用户可获得现金,金额不超过 0.5 元。 (2)贴纸红包,用户可获得一张贴纸,集齐整套贴纸可以换取神秘礼品。 红包有(n-k)/n的概率是现金红包,有 k/n 的概率是贴纸红包。 贴纸共有 k种,用户打开贴纸红包获得每种贴纸的概率相等。 你是摩拜单车公司红包项目的主管,你必须要计算出:一个用户如果想要获 得神秘礼品,那么他期望需要获得的红包数量。 为了避免精度误差,你可能需要计算答案对 p取模的值(p 是质数)。 【输入数据】 一行三个正整数 n、k、p。 【输出数据】 输出数据包括两行。 第一行输出 1 或 2,1 表示你计算了答案的数值,2 表示你计算了答案对 p 取模的值。 如果第一行输出 1,则第二行输出答案的数值(四舍五入到整数);如果第 一行输出 2,则第二行输出答案对 p 取模的值。 【输入输出样例 1】 mobike.in mobike.out 2 1 7 1 2 数据规模对应测试点1。 【输入输出样例 1说明】 红包有 1/2概率是现金红包,有 1/2 概率是贴纸红包,只有一种贴纸。 需要获得的红包数量有 1/2概率是 1, 有 1/4的概率是 2, 有 1/8的概率是 3, 有 1/2^x的概率是 x。 故期望需要获得的红包数量=1/2*1+1/4*2+1/8*3+…=2 【输入输出样例 2】 mobike.in mobike.out 2 1 7 2 2 数据规模对应测试点1。 【输入输出样例 2说明】 同样例 1,答案是 2,答案对 7 取模的值为 2。
设定f[i] 表示 我k种贴纸,收集了i种所需要的数学期望是多少
那么我们假设n=5,k=3; 我们要从f[0]转移到f[1]
我们设这次转移的代价为E 那么我们知道从f[0]->f[1]我们只需要再来一个就可以了,这个贴纸我们是一个一个获得的,而非一下就获得好多个
E=3/5*1+2/5*[E+1]; 数学期望这个概念实在模糊,不妨我们认为就是需要再来几个红包才行
数学期望的公式
这里可以简单理解为,我需要一个红包,一个红包的概率是3/5走一步 剩下我需要走E步,并且我当前这一步没开到红包2/5*[E+1] 所以E是我概率的倒数 同理 我们算出f[2]&f[3]我们可以得到规律,每回的期望其实都是倒数
相当于我计算的是n*(1/k+1/(k-1)+…1) 至于1/k,1/(k-1)怎么计算 可以考虑逆元 我们知道 扩展欧几里得可以求解逆元 1/k相当于k的负一次方 设x为k的负一次方的数论倒数 所以kx=1; kx≡1(modp) 然后根据同余方程里的写法,我们可以求出x 但是这题的数据范围10^7*log2(10^9) 这样的复杂度显然是不合适的 我们考虑还有没有别的方法 o(n)求出 p是我们题目中给的质数 设t=p/i;k=p%i; t*i+k=0(%p) 显然有-t*i=k(%p) 这时候 同时除以i*k -t*逆元(k)=逆元(i) 在modp的意义下 t=p/i; -p/i*逆元(p%i)=逆元(i) 在modp的意义下 为了保证逆元是正的所以 逆元(i)=(p-p/i)*逆元(p%i)
#include
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论,来抢沙发吧~