题目传送门：Problem - D - Codeforces

题意 / Problem

有一颗满二叉树，叶节点个数为\(2^N\)对于每个分支可以选择标记一条边，当A标记完成后，B可以选择修改k条边，请问最终获胜的节点最小是多少？（叶子节点编号为\([1,2^N]\)，如果某个叶子节点可以通过标记的边连接到根节点说明获胜），A希望结果尽可能小，而B希望结果尽可能大。

思路 / Thought

首先思考一个节点修改多少次可以获胜，修改的次数应该是从该节点往上回到根节点的路径上未被标记的边的条数，那么这个条数有多少种可能呢？假如\(N = 3\)，那么就有\(0 1 1 1 2 2 2 3\)这8种情况，那么A为了使得获胜的节点尽可能小，就需要将节点升序排列。如果大的在前面，B就更容易将其修改为获胜的。

观察可以发现，一颗满二叉树，其中未标记的条数应该包含\(0 ~ N\)所有情况并且是按照二项分布的，其实也很好理解，在深度为N的一条路径上选择K个点作为“未标记”的，答案就是\(C_{N}^{K}\)。

现在压力给到B这边，B该如何选择呢，假如有K次修改机会，那么K应该选择“可以修改且最大的”节点来修改，那么这个节点就会是K在二项分布中的最后一个位置。还是假如N = 3，如果K = 2，结果就是7，K = 3，结果就是8。

综上，答案为\(\sum_{i = 0}^{K}C\binom{i}{N}\)。

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 9, p = 1e9 + 7;
int fab[maxn];

int qmi(int a,int b)
{
	int res = 1;
	while(b)
	{
		if(b & 1)res = res * a % p;
		a = a * a % p, b >>= 1;
	}
	return res;
}
int inv(int x){return qmi(x, p - 2);}
int C(int n,int m)
{
	return fab[n] * inv(fab[m] * fab[n - m] % p);
}

void solve()
{
	int N, K;cin >> N >> K;
	if(K > N)K = N;
	//如果K大于N了可以修改任意一个点获胜，和K = N的情况是一样的 
	fab[0] = 1;//处理阶乘 
	for(int i = 1;i <= N; ++ i)fab[i] = fab[i - 1] * i % p;
	
	int ans = 0;
	for(int i = 0; i <= K; ++ i)
		ans = (ans + C(N, i)) % p;
	cout << ans << '\n';
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int _ = 1;
	while(_ --)solve();
	
	return 0;
}