题目

　　https://nanti.jisuanke.com/t/17118

题意

　　有n个点0,1,2...n-1，对于一个点对(i,j)满足i<j，那么连一条边，边权为i xor j，求0到n-1的最大流，结果取模，n<=1e18

分析

　　可以写个最大流对数据找规律，但没找出来……

　　然后只能取分析了，首先最大流等价于最小割

　　明确一定，0->n-1这个要先割掉

　　然后我们贪心，希望有一些点割掉与0相连的边，一些点割掉与n-1相连的边

　　我们去观察每个点与0相连和与n-1相连的两条边权值，容易发现前面若干个左边那条边边权小，后面若干个右边那条边边权小

　　我们可以把前半部分的取左边，后半部分取右边，具体的，分界线就是n-1二进制最高位1对应的数字

　　然后问题就变成求他们的和，第一部分好求，主要第二部分求和

　　转换一下问题，变成了求1 xor x + 2 xor x + 3 xor x + ... + n xor x

　　这里可以数位dp解决，值得注意的是这里数位dp求的是满足数位的和，要先一遍数位dp求出对应状态的数字个数，然后再一遍数位dp求出贡献

最新文章

1. bookstore网上书店测试缺陷报告2
2. 解决: maven编译项目报“非法字符: \65279 ”错误
3. BZOJ4439——[Swerc2015]Landscaping
4. sql left join、right join、inner join
5. WPF线程获取UI线程
6. 用户输出表单处理php
7. 两种动态载入修改后的python模块的方法
8. ref传参时出错
9. C/C++默认浮点型
10. 无法读取配置节 system.serviceModel 因为它缺少节声明的解决方法
11. js的replace的用法；
12. oracle索引(转)
13. LeetCode - 307. Range Sum Query - Mutable
14. Spring Cloud微服务系列文，服务调用框架Feign
15. Quartz+TopShelf实现定时任务
16. [20190226]删除tab$记录的恢复6.txt
17. python---自己来打通节点，链表，栈，应用
18. 穷举法、for循环、函数、作用域、斐波那契数
19. Spring MVC / Boot
20. CSS :after、before、&lt;!DOCTYPE&gt;

热门文章

1. js递归和数组去重(简单便捷的用法)
2. php同时查询两个表的数据
3. LibreOJ #119. 最短路 (堆优化dijkstra)
4. [Python學習筆記] 使用 selenium 抓取網頁並且雙擊滑鼠 (double click)
5. JavaEE-03 JSP数据交互02
6. Ext 6.5.3 classic版本，自定义实现togglefield开关控件
7. luogu P4752
8. 15. PARTITIONS
9. Django reverse函数
10. python测试工具