没做这套,但是看舍友做了。。
考虑f(i)为结尾为i的答案,等于f(i-1) + 1*a(i)^a(0) + 2 * a(i)^a(1) + ...+ (i-1) * a(i) ^ a(i-1)。
所以我们想要个异或的前缀和,前缀和一般是能预处理出来的,但是这里带一个系数,如果a(k) (k<i) 和 a(i)的某一位不相等,它会给k+1次贡献。所以你考虑前i-1个数每一个数在32位里的贡献,每个数k的贡献要乘以系数k+1。具体来说,设zeros[n][32] ones[n][32]为0,a[1]是3,那么ones[1][0] ones[1][1]分别加2,zeros[1][2-32]分别加2。a[i]的某位是0,就跟ones[i-1][那一位]去求,反之亦然。
考虑f(i)为结尾为i的答案,等于f(i-1) + 1*a(i)^a(0) + 2 * a(i)^a(1) + ...+ (i-1) * a(i) ^ a(i-1)。
所以我们想要个异或的前缀和,前缀和一般是能预处理出来的,但是这里带一个系数,如果a(k) (k<i) 和 a(i)的某一位不相等,它会给k+1次贡献。所以你考虑前i-1个数每一个数在32位里的贡献,每个数k的贡献要乘以系数k+1。具体来说,设zeros[n][32] ones[n][32]为0,a[1]是3,那么ones[1][0] ones[1][1]分别加2,zeros[1][2-32]分别加2。a[i]的某位是0,就跟ones[i-1][那一位]去求,反之亦然。
点赞 3 评论 24
全部评论
相关推荐
07-08 12:20
郑州大学 材料工程师 码农索隆:看我帖子https://www.nowcoder.com/discuss/764127692135370752,神州信息那个2B董成杰,我离职的时候,直接干他干了一仗
点赞 评论 收藏
分享
06-12 19:52
吉首大学张家界学院 Python 点赞 评论 收藏
分享
06-14 19:09
门头沟学院 Java darius_:给制造业搞的,什么物料管理生产管理,设备管理点检,最最关键的就是一堆报表看板。个人觉得没啥技术含量都是些基本的crud,但是业务很繁琐那种
点赞 评论 收藏
分享