#P1603. 除夕夜

除夕夜

题目描述

由于 Grisha 去年表现良好,在除夕夜,Ded Moroz 拜访了他,并带来了一大袋礼物!这个袋子里有 nn 颗来自老面包店的甜糖,每颗糖果都标有 11nn 对应其美味度。没有两种糖果的美味相同。

糖果的选择直接影响 Grisha 的幸福。人们可以假设他应该吃最美味的 —— 但是,节日的魔力让事情发生了翻天覆地的变化。重要的是美味度的异或和,而不是普通的总和!

整数序列 a1,a2,...,ama_1, a_2, ..., a_m异或和定义为其所有元素的按位异或:a1a2ama_1 \bigoplus a_2 \bigoplus \dots \bigoplus a_m,这里 \bigoplus 表示按位异或运算。

Ded Moroz 警告 Grisha 他有更多的房子要参观,所以 Grisha 从袋子里拿的糖果数量不能超过 kk。帮助 Grisha 确定他可以获得的最大美味度异或和(最大的异或和意味着最大的快乐!)

输入文件 eve.in

一行两个整数 n,kn,k1kn10181 \le k \le n \le 10^{18}

输出文件 eve.out

一个整数表示 Grisha 可以获得的最大美味度异或和。

4 3
7

一种选择糖果的方案是选择美味度为 1,2,41,2,4 的糖果,美味度的异或和为 77

6 6
7

一种可行方案是选择全部 66 个糖果,美味度的异或和为 77