首页 > 其他 > 详细

ICPC上海 C题 Sum of Log

时间:2020-12-19 18:11:08      阅读:96      评论:0      收藏:0      [点我收藏+]

Pro:
https://codeforces.com/gym/102900/problem/C
给定\(X\),\(Y\)
计算

\[\sum_{i=0}^X \sum_{j=0}^Y [i\&j=0] \lfloor log(i+j)+1 \rfloor \X,Y<=1e9 \1e4组数据 \]

Sol:

易证:

\(i\&j=0\)\(i>=j\)

\(log(i+j)+1=log(i)+1\)

因此

我们可以先把答案拆成

\(i<=X,j<=Y,i>=j\)\(ans\)加上\(i<=Y,j<=Y,i>=j\)\(ans\)

这个玩意可以通过同时数位\(dp\)两个数字来实现

复杂度实现的好一点即可做到\(30*2*2\)

因此总复杂度\(O(T*30*2*2*2)\)

(不妨设X>=Y)

ICPC上海 C题 Sum of Log

原文:https://www.cnblogs.com/Creed-qwq/p/14160170.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!