balcare level
获赞
2
粉丝
0
关注
0
看过 TA
1
浙江大学
2020
大数据开发工程师
IP属地:浙江
暂未填写个人简介
私信
关注
0 点赞 评论 收藏
分享
小仓的射击练习1   时间限制:C/C++语言 1000MS;其他语言 3000MS   内存限制:C/C++语言 65536KB;其他语言 589824KB   题目描述:   小仓酷爱射击运动。今天的小仓会进行N轮射击,已知第i次射击,她击中靶心的概率是a[i] -1 。    小仓想知道N轮射击后,偏离靶心次数为 0 ,1 ,2 次的概率分别是多少。    输入   第一行一个数N,代表射击轮数。     第二行 N个数a[i],第 i个数为a[i]。    1≤N≤100,000     1≤a[i]<998244353    输出   不难证明答案可以表示成一个最简分数 p *...
Jonariguez:mod=998244353,设M是所有ai相乘对mod取余。 次数0:也就是1/M%mod 次数1:求sum{(ai-1)/M | i=1~n|}%mod 次数2:设是第i次和第j次脱靶,那么概率是(ai*aj-ai-aj+1)/M%mod,拆开之后后面三项ai/M aj/M 和1/M对于所有的i和j只需要O(n)就都求出来了,而ai*aj/M虽然看上去是两两组合需要O(n^2),其实只看分子就是a1*(a2+..+an)+a2(a3+..+an)+a3()....,这些通过预处理a数组的后缀和就可以做到O(n)复杂度。需要求逆元,复杂度是log。总的复杂度为O(nlog(mod))
投递美团等公司8个岗位 >
0 点赞 评论 收藏
分享

创作者周榜

更多
关注他的用户也关注了:
牛客网
牛客网在线编程
牛客网题解
牛客企业服务