2020-03-12 22:09
浙江大学 大数据开发工程师 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))
0 点赞 评论 收藏
分享
创作者周榜
更多
关注他的用户也关注了: