cf1717D

D. Madoka and The Corruption Scheme
一道有点意思的题目。
首先对于Madoka给出的任意一颗二叉树，我们可以将其进行调整。使得对于一个节点左边的总是获胜。也就是对于对于每一个子树，左边的最小值小于右边的最小值。
那么要将一个点作为最后的冠军，只需满足它到根，经过的右儿子不超过k即可。
那么只需将1,2,3......依次填到经过右儿子数量为0，经过右儿子的边数量为1的点，这样填肯定是最好的。
那么怎么计数呢，
记f[i]表示从叶子到根经过多少个右儿子。
n=1时 f[0]=1 f[1]=1

n=2时 f[0]=1
f[1]=f[1] (左) +f[0] （右）
f[2]=f[1] (右)
可以发现就是杨辉三角
\(ans=\sum_{i=1}^{min(n,k)}C_{n}^{i}\)

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define A puts("Yes") 
#define B puts("No")
using namespace std;
typedef long long ll;
const int N=2e5+5;
const ll mo=1e9+7;

ll inv[N],f[N],ans;
int n,k;
ll power(ll a,ll b){
	ll t=1,y=a%mo;
	while (b){
		if (b&1) t=t*y%mo;
		y=y*y%mo;
		b/=2;
	}
	return t;
}
ll C(int n,int m){
	return f[n]*inv[m]%mo*inv[n-m]%mo;
	
}
int main(){
	
//	freopen("data.in","r",stdin);		
	scanf("%d %d",&n,&k);
	k=min(n,k);
	
	f[0]=1;
	fo(i,1,n) f[i]=f[i-1]*(ll)i%mo;
	
	inv[n]=power(f[n],mo-2);
	fd(i,n-1,0) inv[i]=inv[i+1]*(ll)(i+1)%mo;

	fo(i,0,k) ans=(ans+C(n,i))%mo;
	printf("%lld\n",ans);
	return 0;
}