4303: Taffy与比赛[hard]

时间限制:1000 ms 内存限制:256 MB
上传者:
提交:24 通过:3

题目描述

有n轮比赛,2n个参赛者。一场比赛是两个参赛者进行比赛,胜者进入下一轮。

在所有比赛开始之前,Taffy可以安排第一轮比赛的参赛者,决定所有比赛的胜者(左边赢还是右边赢)。

比赛开始后,主办方可以操作k次,这个操作是改变某场比赛的胜者。

主办方操作的目的是让赢得比赛的人的编号最大。

Taffy应该怎么安排比赛,才能让主办方操作后赢得比赛的人的编号最小?

输出这个编号,结果对109+7取模




下面给出例子解释:

该例子n=2,k=1。
如下图:


左边的图是Taffy一开始安排的比赛,其中红线代表的是这轮比赛的胜者。

右边的图是主办方操作后的比赛,主办方改变了1和3比赛的结果,让3胜出,这样最后赢的人的编号变成了3。

输入格式

两个整数n,k
1≤n≤105,1≤k≤min(2n−1,109)

输出格式

胜者编号的最小值,结果对109+7取模

输入样例 复制

5 3

输出样例 复制

26

分类标签